Hvad gør et sprog Turing-komplet?

A Turing tarpit er en slags esoterisk programmeringssprog, der stræber efter at være Turing-komplet, mens du bruger så få elementer som muligt. Brainfuck er måske den mest kendte tarpit, men der er mange.

• Iota og Jot er funktionelle sprog med henholdsvis to og tre symboler baseret på SK (I) kombinationsberegning .

• OISC ( En instruktions sætcomputer ) angiver en type tvingende beregning, der kun kræver en instruktion af et eller flere argumenter, normalt “trækker og forgrener, hvis mindre end eller lig med nul”, eller “Træk omvendt fra og spring over, hvis lån”. x86 MMU implementerer den tidligere instruktion og er således Turing-komplet.

Generelt for en tvingende sprog for at være Turing-komplet, det har brug for:

1. En form for betinget gentagelse eller betinget spring (f.eks. while, if + goto)

2. En måde at læse og skrive en eller anden form for lagring på (f.eks. , variabler, tape)

For at et lambda-calculus -baseret funktionelt sprog skal være TC, er det behov:

1. Evnen til at abstrahere funktioner over argumenter (f.eks. lambda-abstraktion, citat)

2. Evnen til at anvende funktioner på argumenter (f.eks. reduktion)

Der er selvfølgelig andre måder at se på beregning på, men disse er almindelige modeller for Turing-tarpits. Bemærk, at ægte computere er ikke universelle Turing-maskiner , fordi de ikke har ubegrænset lagerplads. Strengt taget er de ”afgrænsede lagringsmaskiner”. Hvis du fortsætter med at tilføje hukommelse til dem, ville de asymptotisk nærme sig Turing-maskiner ved magten. Selv selv afgrænsede lagringsmaskiner og finite state-maskiner er imidlertid nyttige til beregning; de er simpelthen ikke universelle .

Strengt taget er I / O ikke påkrævet for Turing-fuldstændighed; TC hævder kun, at et sprog kan beregne den ønskede funktion, ikke at det kan vise dig resultatet. I praksis har ethvert nyttigt sprog en måde at interagere med verden på en eller anden måde.

Kommentarer

• For vigtige sprog er enkle variabler nok? Jeg var under det indtryk, at en eller anden form for samling (f.eks. Arrays eller sammenkædede lister) ville være nødvendig.
• @luiscubal, du skal være i stand til at specificere en vilkårlig mængde data. Med enkle variabler kan du repræsentere mængden af data, som variablerne selv har. Hvad hvis du har brug for at repræsentere N + 1 forskellige stykker data. Man kan argumentere for, at med tricks som Fractran spiller, kan du gøre det selv i enkle variabler … men at ‘ er ikke helt det, du ‘ beder om.
• Er ikke ‘ t det krævede, at sproget skal understøtte ENDLESS sløjfer?
• Re, ” ethvert nyttigt sprog har en måde at interagere med verdenen på. ” Algol 60 havde ingen defineret måde at interagere med verden på. Al din I / O i et Algol 60-program blev udført ved at kalde biblioteksfunktioner, og biblioteksfunktionerne kunne være helt forskellige i forskellige implementeringer. Men jeg fraråder mig hermed enhver diskussion om, hvorvidt Algol 60 var ” nyttigt. ”

Fra et mere praktisk synspunkt: hvis du kan oversætte alle programmer på et Turing-komplet sprog til dit sprog, så (så vidt Jeg ved), dit sprog skal være Turing-komplet.Derfor, hvis du vil kontrollere, om et sprog, du har designet, er Turing-komplet, kan du blot skrive en Brainf *** til YourLanguage-kompilatoren og bevise / demonstrere, at den kan kompilere alle lovlige BF-programmer.

Til præcisere, jeg mener, at ud over en tolk til YourLanguage, skriver du en compiler (på ethvert sprog), der kan kompilere ethvert BF-program til YourLanguage (selvfølgelig med den samme semantik).

Kommentarer

• Ja, det ville helt sikkert være den mest praktiske måde at nærme sig det på. </sarcasm>
• @RobertHarvey har et punkt, men den generelle idé er ret vital. Brainfuck har vist sig at være komplet og meget enkel som programmeringssprog. For ikke-esoteriske programmeringssprog kan implementering af en brainfuck-tolk være meget lettere og hurtigere end at give et strengt bevis ud af ingenting (jeg kan implementere BF i et par linjer af Python, men jeg ‘ m ikke sikker på, hvor jeg skal starte med et formelt bevis for, at Python er turing komplet); og snesevis af esoteriske hjernefnk-inspirerede sprog vides at være komplette, fordi det ‘ ved, hvordan de kortlægges for hjernefuck.
• @RobertHarvey: Hvorfor ikke? En person, der designer deres eget sprog, vil helt sikkert være i stand til at skrive en BF-kompilator til det (hvis det var bydende nødvendigt og ellers finde et passende andet sprog).
• @delnan: Du vil skal dog bevise, at din BF-tolk korrekt implementerer BF-specifikationen, IOW bliver du nødt til at bevise, at din BF-tolk faktisk er en BF-tolk og ikke en tolk til et BF-lignende sprog, der måske eller måske ikke er Turing-komplet.
• @ DarekNędza, at ‘ bare er en naturlig konsekvens af, hvordan Turing-kompletitet er defineret; enhver udvidelse af et Turing Complete-sprog vil stadig være Turing Complete.

Et system kan kun overvejes at være Turing komplet, hvis den kan gøre noget, som en universel Turing-maskine kan. Da den universelle Turing-maskine siges at være i stand til at løse enhver beregningsfunktion givet tid, kan Turing-komplette systemer i forlængelse også gøre det.

For at kontrollere om noget er Turing-komplet, se om du kan implementere en Turing-maskine inde i den. Med andre ord skal du kontrollere, om det kan simulere følgende:

1. Evnen til at læse og skrive “variabler” (eller vilkårlige data) : Næsten meget selvforklarende.
2. Evnen til at simulere flytning af læse- / skrivehovedet : Det er ikke nok til bare at kunne hente og gemme variabler. Det skal også være muligt at simulere muligheden for at flytte båndets hoved for at kunne henvise til andre variabler. Dette kan ofte simuleres inden for programmeringssprog ved brug af array-datastrukturer (eller tilsvarende) eller, i tilfælde af visse sprog såsom maskinkode, muligheden for at henvise til andre variabler ved brug af “pegepinde” (eller tilsvarende).
3. Evnen til at simulere en endelig tilstandsmaskine : Selvom det ikke nævnes ofte, er Turing-maskiner faktisk en variation af finite state-maskiner, der ofte bruges inden for AI-udvikling. Alan Turing sagde, at formålet med staterne er at simulere en persons forskellige måder at løse problemer på.
4. En “stop” -stat : Selvom det ofte nævnes, skal et sæt regler være i stand til at gentage sig selv for at kunne regnes som Turing komplet, det er ikke rigtig et godt kriterium, da den formelle definition af, hvad en algoritme er tilstand, skal algoritmer altid til sidst konkludere. Hvis de ikke kan “konkludere på en eller anden måde, er det enten ikke Turing komplet, eller algoritmen er ikke en beregningsfunktion. Turing komplette systemer, der teknisk set ikke kan slutte på grund af den måde, de fungerer på (som f.eks. Spilkonsoller), kommer omkring denne begrænsning ved at være i stand til at “simulere” en standsningstilstand på en eller anden måde. For ikke at forveksle med det “stopproblem “, en ubestemmelig funktion, der viser, at det er umuligt at opbygge et system, der kunne registrere med 100% pålidelighed, hvis et givet input får et andet system til ikke at afslutte.

Dette er det sande minimum krav til et system, der skal betragtes som Turing komplet. Intet mere, intet mindre. Hvis det ikke kan simulere nogen af disse på en eller anden måde, er det ikke Turing komplet. De metoder, som andre mennesker foreslår, er kun midler til slutningen, da der er flere Turing-komplette systemer, der ikke har disse funktioner.

Bemærk, at der ikke er nogen kendt måde at faktisk opbygge et ægte Turing-komplet system på. Dette skyldes, at der ikke er nogen kendt måde at virkelig simulere Turing-maskinens båndløshed i fysisk rum.

Et programmeringssprog er ved at blive afsluttet, hvis du kan foretage nogen beregning med det.Der er ikke bare et sæt funktioner, der gør et sprog komplet, så svarene siger, at du har brug for sløjfer, eller at du har brug for variabler, er forkerte, da der er sprog, som hverken har men turing komplet.

Alan Turing lavede den universelle turing maskine, og hvis du kan oversætte ethvert program designet til at arbejde på den universelle maskine til at køre på dit sprog, er det også Turing complete. Dette fungerer også indirekte, så du kan sige, at sprog X er komplet, hvis alle programmer til at gennemføre komplet sprog Y kan oversættes til X, da alle universelle programmer til maskinering af turing kan oversættes til et Y-program.

Tidskompleksiteten , rumkompleksitet, let input / output-format og let at skrive ethvert program er ikke inkluderet i ligningen, så en sådan maskine kan teoretisk udføre alle beregninger, hvis beregningerne ikke standses af strømtab eller jorden sluges af solen.

Normalt for at bevise turing fuldstændighed udgør de en tolk for ethvert bevis for at være turing komplet sprog, men for at det skal fungere, har du brug for midler til input og output, to ting der virkelig ikke kræves for at et sprog skal turing complete. Det er nok, at dit program kan ændre tilstanden ved opstart, og at du kan inspicere hukommelsen, efter at programmet er stoppet.

For at få et vellykket sprog behøver det dog mere end at tere fuldstændighed, og dette er sandt for endda turing tarpits. Jeg tror ikke BrainFuck ville have været populær uden , og ..

Kommentarer

• ” Et programmeringssprog er ved at blive afsluttet, hvis du kan foretage nogen beregning med det. ” At ‘ er Church-Turing-afhandlingen, ikke hvad der gør et sprog Turing-komplet.
• @ Rhymoid Så du mener intet er turing komplet, medmindre du kan lave en tolk? Dvs. lambda-calculus er ikke turing komplet, selvom det ‘ s turingækvivalent?
• Jeg ‘ er stadig på udkig efter en autoritativ definition af termerne Turing-ækvivalent og Turing-komplet (og Turing-kraftig). Jeg ‘ Vi har allerede set for mange sager, fra folk på opslagstavler til forskere i deres egen friggin ‘ papirer, der fortolker disse udtryk forskelligt.
• I hvert fald Jeg fortolker ‘ Turing-komplet ‘ som simulering svarende til en Universal Turing Machine (UTM; som igen er i stand til at simulere enhver Turing-maskine – dermed ‘ universal ‘). I Turing ‘ s papir fra 1936, hvor han introducerede sine maskiner, definerede han begrebet UTM og gav en skitse af et bevis på, at UTMer er simulering svarende til Church ‘ s lambda-beregning. Ved at gøre dette beviste han, at de havde den samme beregningskraft. Church-Turing-afhandlingen hævder, enkelt sagt, at ” at ‘ er al den beregningskraft, du ‘ Jeg får nogensinde “.
• Den har to formelle definitioner for Turing-kompletetside på Wikipedia . Den ene kræver I / O, den anden gør ikke ‘ t. Den der ikke ‘ ikke siger, at en maskine turer komplet, hvis den kan beregne hver Turing-beregningsfunktion. Det sætter lambda-calculus tilbage til at være turing komplet, da du nemt kan lave et ækvivalent program i lambda-calculus, der beregner det samme som ethvert turing-maskinprogram.

Du kan ikke fortælle, om det vil løbe uendeligt eller stoppe.

————-

Forklaring: I betragtning af noget input er det umuligt at fortælle i alle tilfælde (ved hjælp af en anden Turing-maskine), om tingene kommer til at løkke uendeligt eller til sidst stoppe, undtagen ved at køre den (hvilket giver dig et svar, hvis det stop, men ikke hvis det løkker!).

Dette betyder, at du skal være i stand til at gemme en potentielt ubegrænset mængde data på en eller anden måde – der skal være et svar til det uendelige bånd, uanset hvordan indviklet! (Ellers er der kun et begrænset antal stater, og så kan du kontrollere, om du tidligere har været igennem denne tilstand og til sidst stopper). Generelt kan Turing-maskiner vokse eller formindske størrelsen af deres tilstand ved hjælp af nogle kontrollerbare midler.

Da Turings originale universelle Turing-maskine har et uløsbart stopproblem, skal din egen Turing-komplette maskine også have en uløselig standsning problem.

Turing komplette systemer kan efterligne ethvert andet Turing komplet system, så hvis du kan bygge en emulator til et velkendt Turing komplet system i dit system, beviser det, at dit system også er Turing komplet.

Antag for eksempel, at du vil bevise, at Slanger & Stiger er Turing komplet, givet et bræt med et uendeligt gentaget gittermønster (med en anden version øverst og venstre side). Ved at vide, at Minsky-maskinen med 2 tællere er Turing komplet (som har 2 ubegrænsede tællere og 1 tilstand ud af et endeligt antal), kan du konstruere et tilsvarende kort, hvor X- og Y-positionen på gitteret er den aktuelle værdi af de 2 tællere og den aktuelle sti er den aktuelle tilstand. Bang! Du har netop bevist, at slanger & Stiger er under Turing.

Kommentarer

• Jeg don ‘ t køb dette argument. Bare fordi stopproblemet er ubeslutsomt for Turing-maskiner, betyder det ikke direkte, at enhver notation, der giver dig mulighed for at specificere et program, som standsningsproblemet er uafgøreligt for, er Turing komplet. Kun det omvendte er åbenlyst sandt: Hvis notationen er Turing komplet, er det naturligvis muligt at skrive programmer, hvor det stoppende problem ikke kan træffes.
• Det ‘ en nødvendig tilstand. Hvis du for hvert program kan beslutte, om det skal stoppes, er sproget ikke ‘ t Turing er fuldført.

En nødvendig betingelse er en sløjfe med et maksimalt iterationstal, der ikke bestemmes foran iteration, eller rekursion, hvor den maksimale rekursionsdybde ikke bestemmes fremad. Som et eksempel, for … i … sløjfer, som du finder dem på mange nyere sprog, er ikke nok til at gøre sprogeturingen komplet (men de vil have andre midler). Bemærk, at dette ikke betyder et begrænset antal gentagelser eller begrænset rekursionsdybde, men at den maksimale iteration og rekursionsdybde skal beregnes fremad.

For eksempel kan Ackermann-funktionen ikke beregnes på et sprog uden På den anden side kan der skrives en masse meget kompleks og meget nyttig software uden at kræve disse funktioner.

På den anden side med hver iterationstælling og hver rekursionsdybde beregnet fremad, ikke kun kan det afgøres, om et program stopper eller ej, men det stopper .

jeg ved, at dette ikke er det formelt korrekte svar, men når du først tager det “minimale” ud af “Turing-complete” og sætter “praktisk” tilbage, hvor det hører hjemme, vil du se de vigtigste funktioner, der adskiller et programmeringssprog fra et markup-sprog er

• variabler
• betingede (hvis / så …)
• loopage (loop / break, while …)

næste com e

• anonyme og navngivne funktioner

for at teste disse påstande, start med et markup-sprog, f.eks. HTML. vi kunne opfinde en HTML + med kun variabler eller kun betingede (MS gjorde det med betingede kommentarer) eller en slags loopkonstruktion (som i mangel af betingelser sandsynligvis ville ende som noget som <repeat n="4">...</repeat>). at gøre nogen af disse vil gøre HTML + betydeligt (?) mere kraftfuld end almindelig HTML, men det ville stadig være mere en markering end et programmeringssprog; med hver ny funktion gør du det mindre af et deklarativt og mere af et tvingende sprog.

søgen efter minimalitet inden for logik og programmering er bestemt vigtig og interessant, men hvis jeg skulle lære n00bies unge eller gamle “hvad er programmering” og “hvordan man lærer at programmere”, ville jeg næppe starte ude med den fulde bredde og bredde af det teoretiske fundament for Turing-fuldstændighed. hele essensen af madlavning og programmering er at lave ting i den rigtige rækkefølge, gentage indtil klar, som din mor gjorde det. det handler om at opsummere det for mig.

så igen, jeg har aldrig afsluttet min CS.

Kommentarer

• Hvis du ikke er sikker, skal du undersøge det først. fractran er gennemført , ligesom brainf * ck . Bemærk også, at html 5 + CSS 3 er Turing komplet, fordi den kan implementere regel 110 .
• ja ja jeg kender. men alle de givne eksempler er mere eller mindre esoteriske (mens de måske er interessante eller overraskende), m Svaret var pragmatisk og sandsynligvis slet ikke minimalt. Jeg synes det ‘ er vigtigt at påpege, at denne side var nr. 1, når man søgte efter Turing-fuldstændighed på google, svarene her er IMHO til ringe brug for f.eks. en n00bie der ønsker at vide, hvad der adskiller HTML fra PHP eller Python. Jeg mener, brainf ck kaldes ikke brainf ck uden grund.