Wat maakt een taal Turing-compleet?

A Turing tarpit is een soort esoterische programmeertaal die ernaar streeft Turing-compleet te zijn met zo min mogelijk elementen. Brainfuck is misschien wel de bekendste tarpit, maar er zijn er veel.

• Iota en Jot zijn functionele talen met respectievelijk twee en drie symbolen, gebaseerd op de SK (I) combinatorcalculus .

• OISC ( One Instruction Set Computer ) geeft een type verplichte berekening aan waarvoor slechts één instructie van een of meer argumenten nodig is, gewoonlijk aftrekken en vertakken indien kleiner dan of gelijk aan nul, of “Omkeren aftrekken en overslaan als lenen”. De x86 MMU implementeert de vorige instructie en is dus Turing-compleet.

In het algemeen, voor een imperatieve taal om Turing-compleet te zijn, heeft het het volgende nodig:

1. Een vorm van voorwaardelijke herhaling of voorwaardelijke sprong (bijv. while, if + goto)

2. Een manier om een vorm van opslag te lezen en te schrijven (bijv. , variabelen, tape)

Voor een lambda-calculus -gebaseerde functionele taal om TC te zijn, behoeften:

1. De mogelijkheid om functies te abstraheren over argumenten (bijv. lambda-abstractie, citaat)

2. De mogelijkheid om functies toe te passen op argumenten (bijv. reductie)

Er zijn natuurlijk andere manieren om naar berekeningen te kijken, maar dit zijn gangbare modellen voor Turing-tarpits. Merk op dat echte computers niet universele Turing-machines zijn omdat ze geen onbeperkte opslagruimte hebben. Strikt genomen zijn het “bounded storage machines”. Als je eraan zou blijven toevoegen, zouden ze asymptotisch de Turing-machines aan de macht benaderen. Maar zelfs machines met begrensde opslag en eindige-toestandsmachines zijn nuttig voor berekeningen; ze zijn gewoon niet universeel .

Strikt genomen is I / O niet vereist voor Turing-volledigheid; TC beweert alleen dat een taal de functie die u wilt berekenen kan berekenen , niet dat hij u het resultaat toont . In de praktijk heeft elke bruikbare taal op de een of andere manier een manier om met de wereld om te gaan.

Opmerkingen

• Zijn eenvoudige variabelen voldoende voor imperatieve talen? Ik had de indruk dat een soort verzameling (bijv. Arrays of gelinkte lijsten) nodig zou zijn.
• @luiscubal je moet een willekeurige hoeveelheid gegevens kunnen specificeren. Met eenvoudige variabelen kunt u de hoeveelheid gegevens weergeven die de variabelen zelf hebben. Wat als u N + 1 verschillende soorten gegevens moet vertegenwoordigen? Je zou kunnen zeggen dat je met trucs zoals Fractran speelt, het zelfs in eenvoudige variabelen zou kunnen doen … maar dat ‘ is niet helemaal wat je ‘ vraagt.
• Isn ‘ Het vereiste dat de taal EINDELOZE loops?
• Re, ” elke bruikbare taal heeft een manier om met de wereld om te gaan. ” Algol 60 had geen gedefinieerde manier om met de wereld om te gaan. Al uw I / O in een Algol 60-programma werd gedaan door bibliotheekfuncties aan te roepen, en de bibliotheekfuncties kunnen compleet anders zijn in verschillende implementaties. Maar hierbij sluit ik mij af van elke discussie of Algol 60 al dan niet ” nuttig was. ”

Vanuit een meer praktisch standpunt: als je alle programmas in een Turing-complete taal in jouw taal kunt vertalen, dan (voor zover Ik weet het), uw taal moet Turing-compleet zijn.Daarom, als je wilt controleren of een door jou ontworpen taal Turing-compleet is, kun je eenvoudig een Brainf *** schrijven naar de YourLanguage-compiler en bewijzen / aantonen dat deze alle legale BF-programmas kan compileren.

Aan verduidelijk, ik bedoel dat je naast een tolk voor YourLanguage, een compiler schrijft (in elke taal) die elk BF-programma kan compileren naar YourLanguage (uiteraard met behoud van dezelfde semantiek).

Opmerkingen

• Ja, dat zou zeker de meest praktische manier zijn om het te benaderen. </sarcasm>
• @RobertHarvey heeft een punt, maar het algemene idee is vrij essentieel. Brainfuck is bewezen volledig te zijn en zeer eenvoudig als programmeertalen gaan. Voor niet-esoterische programmeertalen kan het implementeren van een brainfuck-interpreter veel gemakkelijker en sneller zijn dan een rigoureus bewijs uit het niets geven (ik kan BF implementeren in een paar regels Python, maar ik ‘ m niet zeker waar ik moet beginnen met een formeel bewijs dat Python aan het turen is); en tientallen esoterische hersenneuk-geïnspireerde talen staan erom bekend dat ze compleet zijn, omdat het ‘ s weet hoe ze in verband staan met hersenneuk.
• @RobertHarvey: Waarom niet? Iemand die zijn eigen taal ontwerpt, zou er zeker een BF-compiler naar kunnen schrijven (als het absoluut noodzakelijk was, en anders een geschikte andere taal vinden).
• @delnan: Jij zal moet echter bewijzen dat uw BF-tolk de BF-specificatie correct implementeert, IOW u moet bewijzen dat uw BF-tolk in feite een BF-tolk is en geen tolk voor een BF-achtige taal die al dan niet Turing-compleet.
• @ DarekNędza, dat ‘ slechts een natuurlijk gevolg is van hoe Turing-volledigheid wordt gedefinieerd; elke extensie van een Turing Complete-taal zal nog steeds Turing Complete zijn.

Een systeem kan alleen worden overwogen om Turing compleet te zijn als het alles kan wat een universele Turing-machine kan. Aangezien de universele Turing-machine naar verluidt elke berekenbare functie in een gegeven tijd kan oplossen, kunnen Turing-complete systemen dat bij uitbreiding ook doen.

Om te controleren of iets Turing compleet is, kijk of je kan er een Turing-machine in implementeren. Met andere woorden, controleer of het het volgende kan simuleren:

1. De mogelijkheid om “variabelen” (of willekeurige gegevens) te lezen en te schrijven : spreekt voor zich.
2. De mogelijkheid om het verplaatsen van de lees- / schrijfkop te simuleren : Het is niet “genoeg om variabelen alleen op te halen en op te slaan. Het moet ook mogelijk zijn om de mogelijkheid om de kop van de tape te bewegen te simuleren om naar andere variabelen te verwijzen. Dit kan binnen programmeertalen vaak worden gesimuleerd met behulp van array-datastructuren (of equivalent) of, in het geval van bepaalde talen, zoals machinecode, de mogelijkheid om naar andere variabelen te verwijzen door het gebruik van “pointers” (of equivalent).
3. De mogelijkheid om een eindige-toestandsmachine te simuleren : hoewel niet vaak genoemd, zijn Turing-machines eigenlijk een variatie van de eindige-toestandsmachines die vaak worden gebruikt binnen AI-ontwikkeling. Alan Turing zei dat het doel van de staten is om iemands “verschillende manieren om problemen op te lossen” te simuleren.
4. Een “halt” state : Hoewel het vaak wordt genoemd, moet een reeks regels zichzelf kunnen herhalen om te tellen als een complete Turing, maar dat is niet echt een goed criterium sinds de formele definitie van wat een algoritme is toestand algoritmen moeten uiteindelijk altijd concluderen. Als ze op de een of andere manier niet kunnen concluderen, is de Turing niet compleet, of is het algoritme geen berekenbare functie. Turing van complete systemen die technisch gezien niet kunnen concluderen vanwege de manier waarop ze werken (zoals bijvoorbeeld gameconsoles), omzeilen deze beperking door op de een of andere manier een stilstandtoestand te kunnen simuleren. Niet te verwarren met het stopprobleem “, een onbeslisbare functie die bewijst dat het” onmogelijk is om een systeem te bouwen dat met 100% betrouwbaarheid kan detecteren of een gegeven invoer ertoe leidt dat een ander systeem niet tot een conclusie komt.

Dit zijn het echte minimum. vereisten voor een systeem om als Turing als compleet te worden beschouwd. Niets meer niets minder. Als het deze op de een of andere manier niet kan simuleren, is het Turing niet compleet. De methoden die andere mensen hebben voorgesteld, zijn slechts een middel om het doel te bereiken, aangezien er verschillende Turing complete systemen zijn die deze eigenschappen niet hebben.

Merk op dat er geen bekende manier is om daadwerkelijk een echt Turing compleet systeem te bouwen Dit komt omdat er “geen bekende manier is om de grenzeloosheid van de tape van de Turing-machine in de fysieke ruimte echt te simuleren.

Een programmeertaal is voltooid als je er een berekening mee kunt maken.Er is niet slechts één set functies die een taal compleet maken, dus antwoorden die zeggen dat je loops nodig hebt of dat je variabelen nodig hebt, kloppen niet, aangezien er talen zijn die geen van beide hebben maar zijn voltooid.

Alan Turing heeft de universele turingmachine gemaakt en als je een programma kunt vertalen dat is ontworpen om op de universele machine te werken om in jouw taal te draaien, is het ook Turing compleet. Dit werkt ook indirect, zodat u kunt zeggen dat taal X voltooid is als alle programmas voor het testen van volledige taal Y kunnen worden vertaald voor X, aangezien alle universele programmas voor turingmachines kunnen worden vertaald naar een Y-programma.

De tijdcomplexiteit , ruimtecomplexiteit, eenvoudig invoer / uitvoerformaat en eenvoudig schrijven, elk programma is niet in de vergelijking opgenomen, dus zon machine kan theoretisch alle berekeningen doen als de berekeningen niet worden gestopt door vermogensverlies of de aarde wordt opgeslokt door de zon.

Gewoonlijk om de volledigheid te bewijzen, maken ze een tolk voor elke bewezen volledige taal, maar om het te laten werken heb je middelen voor invoer en uitvoer nodig, twee dingen die echt niet nodig zijn om een taal volledig te laten zijn. Het is voldoende dat uw programma de status bij het opstarten kan wijzigen en dat u het geheugen kunt inspecteren nadat het programma is gestopt.

Om een succesvolle taal te maken heeft het echter meer nodig dan alleen de volledigheid, en dit is geldt voor gelijkmatige tarpits. Ik denk niet dat BrainFuck populair zou zijn geweest zonder , en ..

Reacties

• ” Een programmeertaal is aan het werken als je een berekening kunt maken ermee. ” Dat ‘ is de thesis van de Kerk-Turing, niet wat een taal Turing-compleet maakt.
• @Rhymoid Dus je bedoelt dat niets is voltooid tenzij je een tolk kunt maken? Dat wil zeggen dat de lambda-calculus niet volledig is, zelfs niet als het ‘ de gelijkmaker is?
• Ik ‘ ben nog steeds op zoek naar een gezaghebbende definitie van de termen Turing-equivalent en Turing-compleet (en Turing-krachtig). I ‘ heb al te veel gevallen gezien, van mensen op prikborden tot onderzoekers in hun eigen ‘ papers, die deze termen anders interpreteren.
• Hoe dan ook, Ik interpreteer ‘ Turing-complete ‘ als simulatie equivalent aan een Universal Turing Machine (UTM; die op zijn beurt elke Turing-machine kan simuleren – vandaar ‘ universeel ‘). In Turing ‘ s paper uit 1936, waarin hij zijn machines introduceerde, definieerde hij het begrip UTM en gaf een schets van een bewijs dat UTMs simulatie-equivalent zijn aan Church ‘ s lambda-calculus. Hiermee bewees hij dat ze dezelfde rekenkracht hadden. De thesis van Church-Turing beweert, eenvoudig gezegd, dat ” dat ‘ alle rekenkracht bevat die u ‘ zal ooit ” krijgen.
• Het heeft twee formele definities voor Turing volledigheidspagina van Wikipedia . De ene vereist I / O, de andere niet ‘ t. Degene die niet ‘ zegt dat een machine aan het turen is als hij elke Turing-berekenbare functie kan berekenen. Dat maakt de lambda-calculus weer compleet, aangezien je gemakkelijk een gelijkwaardig programma in lambda-calculus kunt maken dat hetzelfde berekent als alle andere turing-machineprogrammas.

Je kunt “niet zeggen of het” oneindig zal doorlopen of stoppen.

————-

Uitleg: Gegeven wat input, is het onmogelijk om in elk geval (met een andere Turing-machine) te zeggen of het ding oneindig zal doorlopen of uiteindelijk zal stoppen, behalve door het uit te voeren (wat je een antwoord geeft als het stop, maar niet als het wordt herhaald!).

Dit betekent dat je op de een of andere manier een potentieel onbeperkte hoeveelheid gegevens moet kunnen opslaan – er moet een equivalent zijn voor de oneindige tape, ongeacht hoe ingewikkeld! (Anders is er maar een eindig aantal toestanden en dan kun je controleren of je die toestand eerder hebt doorgemaakt en uiteindelijk stopt). Over het algemeen kunnen Turing-machines de omvang van hun staat met controleerbare middelen vergroten of verkleinen.

Aangezien de originele universele Turing-machine van Turing een onoplosbaar stopprobleem heeft, moet uw eigen complete Turing-machine ook een onoplosbare stop hebben. probleem.

Turing complete systemen kunnen elk ander Turing compleet systeem emuleren, dus als je een emulator kunt bouwen voor een bekend Turing compleet systeem in je systeem, bewijst dat dat je systeem ook Turing compleet is.

Stel dat je bijvoorbeeld wilt bewijzen dat Snakes & Ladders Turing compleet is, gegeven een bord met een oneindig herhaald rasterpatroon (met een andere versie bovenaan en linkerkant). Wetende dat de Minsky-machine met 2 tellers Turing compleet is (die 2 onbeperkte tellers heeft en 1 staat uit een eindig aantal), kun je een gelijkwaardig bord construeren waarbij de X- en Y-positie op het raster de huidige waarde van de 2 tellers is en het huidige pad is de huidige staat. Bang! Je hebt zojuist bewezen dat Snakes & Ladders Turing compleet zijn.

Reacties

• Ik don ‘ koop dat argument niet. Alleen omdat het stopprobleem onbeslisbaar is voor Turing-machines, betekent niet direct dat elke notatie waarmee je een programma kunt specificeren waarvoor het stopprobleem onbeslisbaar is, Turing compleet is. Alleen het omgekeerde is duidelijk waar: als de notatie Turing compleet is, dan is het natuurlijk mogelijk om programmas te schrijven waarvan het stopprobleem onbeslisbaar is.
• Het ‘ een noodzakelijke voorwaarde. Als je voor elk programma kunt beslissen of het stopt, dan is de taal n ‘ t Turing compleet.

Een noodzakelijke voorwaarde is een lus met een maximale iteratietelling die niet voorafgaand aan de iteratie wordt bepaald, of recursie waarbij de maximale recursiediepte niet van tevoren wordt bepaald. Als voorbeeld, voor … in … lussen zoals je ze in veel nieuwere talen aantreft, zijn niet genoeg om de taal compleet te maken (maar ze zullen andere middelen hebben). Merk op dat dit niet een beperkt aantal iteraties of een beperkte recursiediepte betekent, maar dat de maximale iteraties en recursiediepte vooruit moeten worden berekend.

De Ackermann-functie kan bijvoorbeeld niet worden berekend in een taal zonder Aan de andere kant kan veel zeer complexe en zeer nuttige software worden geschreven zonder dat deze functies nodig zijn.

Aan de andere kant, waarbij elke iteratie telt en elke recursiediepte vooruit wordt berekend, niet alleen kan worden besloten of een programma zal stoppen of niet, maar het zal stoppen.

ik weet dat dit formeel niet het juiste antwoord is, maar als je eenmaal het minimale uit Turing-complete haalt en praktisch terugzet waar het hoort, zie je de belangrijkste kenmerken die een programmeertaal onderscheiden van een opmaaktaal zijn

• variabelen
• conditionals (if / then …)
• loopage (loop / break, while …)

volgende com e

• anonieme en benoemde functies

om deze beweringen te testen, begint u met een opmaaktaal, bijvoorbeeld HTML. we zouden een HTML + kunnen verzinnen met alleen variabelen, of alleen conditionals (MS deed dat met voorwaardelijke commentaren), of een soort lusconstructie (die bij afwezigheid van conditionals waarschijnlijk zou eindigen als iets als <repeat n="4">...</repeat>). door een van deze dingen te doen, wordt HTML + aanzienlijk (?) krachtiger dan gewone HTML, maar het zou nog steeds meer een opmaak dan een programmeertaal zijn; met elke nieuwe functie maak je het minder een declaratieve en meer een imperatieve taal.

de zoektocht naar minimaliteit in logica en programmeren is zeker belangrijk en interessant, maar als ik n00bies jong of oud moest leren “wat is programmeren” en “hoe te leren programmeren”, dan zou ik nauwelijks beginnen uit met de volledige breedte en breedte van de theoretische grondslagen van de volledigheid van Turing. de hele essentie van koken en programmeren is dingen doen, in de juiste volgorde, herhalen tot ze klaar zijn, zoals je moeder het deed. dat vat het ongeveer voor mij samen. / p>

nogmaals, ik heb mijn CS nooit afgemaakt.

Opmerkingen

• Als je het niet zeker weet, moet je het eerst onderzoeken. fractran is turing voltooid , net als brainf * ck . Merk ook op dat html 5 + CSS 3 Turing voltooid is omdat het regel 110 .
• ja ja ja ik weet het. maar alle gegeven voorbeelden zijn min of meer esoterisch (hoewel misschien interessant of verrassend), m Het antwoord was pragmatisch en zeer waarschijnlijk helemaal niet minimaal. ik denk dat het ‘ s belangrijk is om erop te wijzen – deze pagina was # 1 bij het zoeken naar Turing-volledigheid op Google, de antwoorden hier zijn IMHO van weinig nut voor, laten we zeggen, een n00bie wie wil weten wat HTML onderscheidt van PHP of Python. ik bedoel, brainf ck wordt niet voor niets brainf ck genoemd.