Vad gör ett språk Turing-komplett?

A Turing tarpit är ett slags esoteriskt programmeringsspråk som strävar efter att vara Turing-komplett medan man använder så få element som möjligt. Brainfuck är kanske den mest kända tarpit, men det finns många.

• Iota och Jot är funktionella språk med två respektive tre symboler, baserat på SK (I) combinator calculus .

• OISC ( En instruktionsuppsättningsdator ) betecknar en typ av tvingande beräkning som endast kräver en instruktion av ett eller flera argument, vanligtvis ”subtrahera och förgrena sig om mindre än eller lika med noll”, eller ”Omvänd subtrahera och hoppa över om lån”. x86 MMU implementerar den tidigare instruktionen och är därmed Turing-komplett.

I allmänhet för en tvingande språk för att vara Turing-komplett, det behöver:

1. En form av villkorlig upprepning eller villkorligt hopp (t.ex. while, if + goto)

2. Ett sätt att läsa och skriva någon form av lagring (t.ex. , variabler, tejp)

För att ett lambda-calculus -baserat funktionellt språk ska vara TC, är det behov:

1. Förmågan att abstrakta funktioner över argument (t.ex. lambda-abstraktion, citat)

2. Förmågan att tillämpa funktioner på argument (t.ex. reduktion)

Det finns naturligtvis andra sätt att titta på beräkning, men det här är vanliga modeller för Turing-tarpits. Observera att riktiga datorer är inte universella Turing-maskiner eftersom de inte har obegränsat lagringsutrymme. Strängt taget är de ”begränsade lagringsmaskiner”. Om du fortsätter att lägga till minne till dem skulle de utan problem närma sig Turing-maskiner vid makten. Men även begränsade lagringsmaskiner och finite state-maskiner är användbara för beräkning; de är helt enkelt inte universella .

Strikt taget är I / O inte nödvändigt för Turing-fullständighet; TC hävdar bara att ett språk kan beräkna den funktion du vill ha, inte att det kan visa dig resultatet. I praktiken har varje användbart språk ett sätt att interagera med världen på något sätt.

Kommentarer

• För tvingande språk räcker det med enkla variabler? Jag hade intrycket av att det skulle behövas någon form av samling (t.ex. arrays eller länkade listor).
• @luiscubal du måste kunna ange en godtycklig mängd data. Med enkla variabler kan du representera mängden data som variablerna själva har. Vad händer om du behöver representera N + 1 olika data. Man kan argumentera för att med tricks som Fractran spelar kan du göra det även i enkla variabler … men att ’ är inte riktigt vad du ’ frågar.
• Är inte ’ t krävs att språket måste stödja ENDLESS loopar?
• Re, ” varje användbart språk har ett sätt att interagera med världen. ” Algol 60 hade inget definierat sätt att interagera med världen. Alla dina I / O i ett Algol 60-program gjordes genom att ringa biblioteksfunktioner, och biblioteksfunktionerna kunde vara helt olika i olika implementeringar. Men jag hämtar mig härmed från alla diskussioner om huruvida Algol 60 var ” användbart. ”

Från en mer praktisk synpunkt: om du kan översätta alla program på ett Turing-komplett språk till ditt språk, då (så långt som Jag vet), ditt språk måste vara Turing-komplett.Därför, om du vill kontrollera om ett språk du designade är Turing-komplett, kan du helt enkelt skriva en Brainf *** till YourLanguage-kompilatorn och bevisa / visa att den kan sammanställa alla lagliga BF-program.

Till klargöra, jag menar att förutom en tolk för YourLanguage, skriver du en kompilator (på vilket språk som helst) som kan kompilera vilket BF-program som helst till YourLanguage (naturligtvis med samma semantik).

Kommentarer

• Ja, det skulle definitivt vara det mest praktiska sättet att närma sig det. </sarcasm>
• @RobertHarvey har en poäng, men den allmänna idén är ganska viktig. Brainfuck har visat sig vara turing-komplett och väldigt enkelt när programmeringsspråken går. För icke-esoteriska programmeringsspråk kan det vara mycket enklare och snabbare att implementera en brainfuck-tolk än att ge ett strikt bevis från ingenstans (jag kan implementera BF i ett par rader av Python, men jag ’ m inte säker på var jag ska börja med ett formellt bevis på att Python turerar fullständigt); och dussintals esoteriska hjärnknull-inspirerade språk är kända för att vara turing kompletta eftersom det ’ känner till hur de kartläggs för hjärna.
• @RobertHarvey: Varför inte? Visst skulle någon som utformade sitt eget språk kunna skriva en BF-kompilator till det (om det var absolut nödvändigt och hitta ett lämpligt annat språk annars).
• @delnan: Du kommer måste dock bevisa att din BF-tolk korrekt implementerar BF-specifikationen, IOW måste du bevisa att din BF-tolk faktiskt är en BF-tolk och inte en tolk för ett BF-liknande språk som kanske eller inte kan vara Turing-komplett.
• @ DarekNędza, att ’ är bara en naturlig konsekvens av hur Turing Fullständighet definieras; alla förlängningar av ett Turing Complete-språk kommer fortfarande att vara Turing Complete.

Ett system kan bara övervägas att vara Turing komplett om den kan göra något som en universell Turing-maskin kan. Eftersom den universella Turing-maskinen sägs kunna lösa vilken beräkningsbar funktion som helst, kan Turing-kompletta system också göra det.

För att kontrollera om något är Turing komplett, se om du kan implementera en Turing-maskin inuti den. Med andra ord, kontrollera om det kan simulera följande:

1. Möjligheten att läsa och skriva ”variabler” (eller godtyckliga data) : Ganska mycket självförklarande.
2. Möjligheten att simulera flyttning av läs- / skrivhuvudet : Det räcker inte för att bara kunna hämta och lagra variabler. Det måste också vara möjligt att simulera möjligheten att flytta bandets huvud för att referera till andra variabler. Detta kan ofta simuleras inom programmeringsspråk med användning av array-datastrukturer (eller motsvarande) eller, i fallet med vissa språk som maskinkod, möjligheten att referera till andra variabler genom användning av ”pekare” (eller motsvarande).
3. Möjligheten att simulera en maskin med ändligt tillstånd : Även om det inte nämns ofta är Turing-maskiner faktiskt en variation av finite state-maskiner som ofta används inom AI-utveckling. Alan Turing sa att syftet med staterna är att simulera en persons olika sätt att lösa problem.
4. En ”stopp” -stat : Även om det ofta nämns måste en uppsättning regler kunna upprepa sig för att kunna räknas som Turing komplett, det är inte riktigt ett bra kriterium eftersom den formella definitionen av vad en algoritm är tillstånd algoritmer måste alltid så småningom avslutas. Om de inte kan sluta på något sätt är det antingen inte Turing komplett eller så är algoritmen inte en beräkningsbar funktion. Turing kompletta system som tekniskt inte kan sluta på grund av hur de fungerar (som spelkonsoler, till exempel) kommer runt denna begränsning genom att kunna ”simulera” ett stoppläge på något sätt. För att inte förväxlas med ”stoppproblemet” ”, en obestämbar funktion som visar att det är omöjligt att bygga ett system som kan upptäcka med 100% tillförlitlighet om en given ingång kommer att leda till att ett annat system inte slutar.

Det här är det sanna minimumet krav för att ett system ska betraktas som Turing komplett. Varken mer eller mindre. Om den inte kan simulera någon av dessa på något sätt är det inte Turing komplett. De metoder som andra föreslog är bara medel till slutet eftersom det finns flera Turing-kompletta system som inte har dessa funktioner.

Observera att det inte finns något känt sätt att faktiskt bygga ett riktigt Turing-komplett system . Detta beror på att det inte finns något känt sätt att verkligen simulera Turing-maskinens bandlöshet i fysiskt utrymme.

Ett programmeringsspråk är slutfört om du kan göra någon beräkning med det.Det finns inte bara en uppsättning funktioner som gör att språket blir fullständigt så att du säger att du behöver slingor eller att du behöver variabler är fel eftersom det finns språk som inte har någon men håller på att slutföra.

Alan Turing skapade den universella turingmaskinen och om du kan översätta alla program som är utformade för att fungera på den universella maskinen för att köra på ditt språk är det också Turing complete. Detta fungerar också indirekt så att du kan säga att språk X är turing komplett om alla program för turing komplett språk Y kan översättas för X eftersom alla universella turing maskinprogram kan översättas till ett Y-program.

Tids komplexitet , rymdkomplexitet, lätt inmatnings- / utdataformat och lätt att skriva vilket program som helst ingår inte i ekvationen, så en sådan maskin kan teoretiskt göra alla beräkningar om beräkningarna inte stoppas av strömavbrott eller jorden sväljs av solen.

Vanligtvis för att bevisa turingens fullständighet gör de en tolk för alla bevisade att de turerar hela språket, men för att det ska fungera behöver du in- och utdata, två saker som verkligen inte krävs för att ett språk ska vara turing komplett. Det räcker för att ditt program kan ändra tillståndet vid start och att du kan inspektera minnet efter att programmet har stoppats.

För att göra ett framgångsrikt språk behöver det dock mer än att tyras fullständigt och detta är sant för även turing tarpits. Jag tror inte BrainFuck skulle ha varit populärt utan , och ..

Kommentarer

• ” Ett programmeringsspråk är turing komplett om du kan göra någon beräkning med det. ” Att ’ är Church-Turing-avhandlingen, inte vad som gör ett språk Turing-komplett.
• @ Rhymoid Så du menar att ingenting är turing komplett om du inte kan göra tolk? Dvs. lambda-kalkyl är inte turing komplett även om den ’ s turingekvivalent?
• Jag ’ jag letar fortfarande efter en auktoritär definition av termerna Turing-ekvivalent och Turing-komplett (och Turing-kraftfull). Jag ’ Vi har redan sett för många fall, från personer på anslagstavlor till forskare i sina egna friggin ’ papper, som tolkar dessa termer annorlunda.
• Hur som helst, Jag tolkar ’ Turing-komplett ’ som simulering motsvarande en Universal Turing Machine (UTM; som i sin tur kan simulera vilken Turing-maskin som helst – därmed ’ universal ’). I Turing ’ s papper från 1936, där han introducerade sina maskiner, definierade han begreppet UTM och gav en skiss av ett bevis på att UTM är simulering motsvarande kyrkan ’ s lambdakalkyl. Genom att göra detta bevisade han att de hade samma beräkningskraft. Church-Turing-avhandlingen hävdar, enkelt uttryckt, att ” att ’ är all beräkningskraft som du ’ Jag kommer någonsin att få ”.
• Den har två formella definitioner för Turing-fullständighetens sida på Wikipedia . En kräver I / O, den andra behöver inte ’ t. Den som inte ’ t säger att en maskin turerar komplett om den kan beräkna varje Turing-beräknbar funktion. Det gör att lambdakalkylen återgår till att vara turing komplett eftersom du enkelt kan göra ett ekvivalentprogram i lambdakalkyl som beräknar samma som alla turingmaskinsprogram.

Du kan inte se om det kommer att gå oändligt eller stoppa.

————-

Förklaring: Med tanke på lite input är det omöjligt att säga i alla fall (med en annan Turing-maskin) om saken kommer att gå oändligt eller slutligen sluta, förutom genom att köra den (vilket ger dig svar om det gör sluta, men inte om det slingrar!).

Detta innebär att du måste kunna lagra en potentiellt obegränsad mängd data på något sätt – det måste finnas en motsvarighet till det oändliga bandet, oavsett hur invecklad! (Annars finns det bara ett begränsat antal stater och sedan kan du kontrollera om du har gått igenom det tillståndet tidigare och så småningom slutat). Generellt kan Turing-maskiner växa eller krympa storleken på deras tillstånd på något kontrollerbart sätt.

Eftersom Turings ursprungliga universella Turing-maskin har ett olösligt stoppproblem måste din egen Turing-kompletta maskin också ha en olöslig stoppning problem.

Turing-kompletta system kan emulera alla andra Turing-kompletta system, så om du kan bygga en emulator för ett välkänt Turing-komplett system i ditt system, bevisar att ditt system också är Turing-komplett.

Antag till exempel att du vill bevisa att Ormar & Stegar är Turing komplett, med en tavla med ett oändligt upprepat rutmönster (med en annan version på toppen och vänster sida). Att veta att 2-räknaren Minsky-maskinen är Turing komplett (som har 2 obegränsade räknare och ett tillstånd av ett begränsat antal), kan du konstruera ett motsvarande kort där X- och Y-positionen på nätet är det aktuella värdet för de 2 räknarna och den aktuella vägen är det aktuella tillståndet. Smäll! Du har precis bevisat att Ormar & Stegar är turing kompletta.

Kommentarer

• Jag don ’ t köp det argumentet. Bara för att stoppproblemet är obeslutbart för Turing-maskiner betyder inte direkt att varje notation som låter dig ange ett program för vilket stoppproblemet är obestämbart är Turing komplett. Endast det inversa är uppenbarligen sant: Om notationen är Turing komplett, är det naturligtvis möjligt att skriva program för vilka det stoppande problemet är obeslutbart.
• Det ’ ett nödvändigt villkor. Om du kan bestämma för varje program om det ska stoppas, är språket inte ’ t Turing komplett.

Ett nödvändigt villkor är en slinga med ett maximalt iterationsantal som inte bestäms före iterationen, eller rekursion där det maximala rekursionsdjupet inte bestäms framåt. Som ett exempel, för … i … slingor som du hittar dem på många nyare språk räcker det inte för att språket blir fullständigt (men de kommer att ha andra medel). Observera att detta inte betyder ett begränsat antal iterationer eller begränsat rekursionsdjup, men att maximala iterationer och rekursionsdjup måste beräknas framåt.

Exempelvis kan Ackermann-funktionen inte beräknas på ett språk utan Å andra sidan kan mycket mycket komplex och mycket användbar programvara skrivas utan att dessa funktioner krävs.

Å andra sidan, med varje iterationsräkning och varje rekursionsdjup beräknat framåt, inte bara kan det bestämmas om ett program ska stoppas eller inte, men det kommer att stoppa.

jag vet att detta inte är det formellt korrekta svaret, men när du tar det ”minimala” ur ”Turing-complete” och lägger ”praktiskt” tillbaka där det hör hemma, kommer du att se de viktigaste funktionerna som skiljer ett programmeringsspråk från ett markeringsspråk är

• variabler
• villkor (om / då …)
• loopage (loop / break, medan …)

nästa com e

• anonyma och namngivna funktioner

för att testa dessa påståenden, börja med ett markeringsspråk, säg HTML. vi kunde uppfinna en HTML + med endast variabler, eller endast villkor (MS gjorde det med villkorliga kommentarer) eller någon form av loopkonstruktion (som i avsaknad av villkor troligen skulle hamna som <repeat n="4">...</repeat>). att göra något av dessa kommer att göra HTML + betydligt (?) kraftfullare än vanlig HTML, men det skulle fortfarande vara mer en markering än ett programmeringsspråk; med varje ny funktion gör du det mindre av ett deklarativt och mer av ett tvingande språk.

strävan efter minimalitet i logik och programmering är säker och viktig, men om jag var tvungen att lära n00bies unga eller gamla ”vad programmerar” och ”hur man lär sig att programmera”, skulle jag knappast börja ut med hela bredden och bredden av de teoretiska grunderna för Turing-fullständighet. hela kärnan i matlagning och programmering är att göra saker, i rätt ordning, upprepa tills det är klart, som din mamma gjorde det. det sammanfattar det för mig.

sedan igen, jag avslutade aldrig min CS.

Kommentarer

• Om du inte är säker bör du undersöka det först. fractran är fullbordad , liksom brainf * ck . Observera också att html 5 + CSS 3 är Turing komplett eftersom det kan implementera regel 110 .
• ja ja jag vet. men alla exemplen som ges är mer eller mindre esoteriska (medan de kanske är intressanta eller överraskande), m svaret var ett pragmatiskt och mycket troligtvis inte minimalt alls. Jag tycker att det ’ är viktigt att påpeka det – den här sidan var # 1 när man letade efter Turing-fullständighet på google, svaren här är IMHO till liten nytta för, säg, en n00bie som vill veta vad som skiljer HTML från PHP eller Python. jag menar att hjärnf ck inte kallas hjärnf ck utan anledning.