Turingvolledigheid: wat een taal kan uitdrukken
Een taal of rekenmodel is turingvolledig als het elke turingmachine kan nabootsen. Het gaat om de berekeningen die je kunt beschrijven, met geheugen dat zonder vaste bovengrens kan groeien en zonder vaste tijdslimiet. Het belooft geen snelle uitvoering of onbeperkte hardware. Zie Cornells uitleg over rekenmodellen (Engels).
Een klein programma om over na te denken
Dit Pliro-programma onthoudt een waarde, controleert een voorwaarde en herhaalt een stap:
# taal: nl
laat remaining = 3
zolang remaining > 0:
zeg remaining
zet remaining = remaining - 1
zeg "Ready!"
Voorspel de uitvoer voordat je het start: drie getallen, gevolgd door een bericht. Verander de beginwaarde in vijf. Probeer daarna nul.
Variabelen, keuzes en herhaling zijn handige bouwstenen voor algemene programma’s. Dit voorbeeld laat alleen aftellen zien; het is geen bewijs van turingvolledigheid. Ook een lus die nooit stopt, zou op zichzelf onvoldoende bewijs zijn.
Wat betekent het niet?
“Het kan ieder probleem oplossen.” Voor sommige vragen bestaat geen algoritme dat voor elke invoer altijd het juiste antwoord geeft. Het stopprobleem vraagt of een willekeurig programma bij een gegeven invoer uiteindelijk stopt. Er bestaat geen algoritme dat zelf altijd stopt en deze vraag correct beantwoordt voor alle programma’s en invoeren in een universeel model. Zie Cornells uitleg over onbeslisbaarheid (Engels).
“Het kan tekenen of internet gebruiken.” Daarvoor zijn mogelijkheden nodig van de uitvoerlaag en uitvoeromgeving. De berekeningen die een taal kan beschrijven, geven op zichzelf geen toegang tot een scherm, bestand of netwerk.
“Het slaagt voor de turingtest.” Die test gaat over het nabootsen van een menselijk gesprek, een ander onderwerp. Lees Alan Turing.
Hoe zit dat bij Pliro?
Pliro heeft variabelen, voorwaarden, lussen, functies en verzamelingen. Daarmee kun je steeds uitgebreidere programma’s maken. Engelse en Nederlandse syntaxis beschrijven dezelfde onderliggende bewerkingen.
Een echte Pliro-sessie heeft eindig geheugen en uitvoerlimieten, waaronder instructiebudgetten en grenzen aan geneste functieaanroepen. Een drukke lus kan met een foutmelding worden gestopt. Bij het uitvoeren van je code gelden die praktische regels.
Een formele uitspraak dat Pliro turingvolledig is, vereist een precies model, expliciete aannames over beschikbare middelen en een bewijs dat het een universele machine kan nabootsen. Een lijst taalfuncties bewijst dat niet, en dit artikel geeft zo’n bewijs niet.
Begin voor je eigen project met concrete vragen: kan het programma de informatie voorstellen, de beslissingen nemen en de benodigde mogelijkheden van de omgeving gebruiken?
Lussen laten stoppen · Afgeschermde uitvoering · Compiler en interpreter