Turingvolledigheid

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de berekenbaarheidstheorie wordt een programmeertaal, of een ander systeem om bewerkingen mee uit te drukken, Turing-volledig (vaker: Turing-compleet) genoemd als het de uitdrukkingskracht heeft van een universele Turingmachine. Dat betekent ruwweg dat elke berekening of gegevensbewerking die geprogrammeerd kan worden, ook in dit systeem geprogrammeerd kan worden.

Het woord verwijst naar de wiskundige Alan Turing, die de Turingmachine als algemene maatstaf van berekenbaarheid heeft uitgevonden.

Nadere omschrijving[bewerken]

Turing-volledigheid heeft betrekking op systemen waarin afbeeldingen kunnen worden gespecificeerd. Zo'n afbeelding kan worden beschouwd als een bewerking die invoer van een bepaalde vorm omzet in uitvoer van een bepaalde (mogelijk andere) vorm, zodanig dat gegeven de invoer de uitvoer vaststaat.

Turingmachines zijn zelf zo'n systeem: elke Turingmachine specificeert een bewerking op eindige reeksen symbolen.

Een systeem is Turing-volledig als met de specificaties die in het systeem gedefinieerd kunnen worden de werking van Turingmachines te simuleren is. Zo'n simulatie bestaat uit drie afbeeldingen:

  • een afbeelding van eindige symboolreeksen naar mogelijke invoeren van (de specificaties in) het systeem;
  • een afbeelding van eindige symboolreeksen naar mogelijke uitvoeren van (de specificaties in) het systeem;
  • een afbeelding van Turingmachines naar specificaties in het systeem, zodanig dat voor elke Turingmachine deze drie afbeeldingen, na elkaar toegepast, dezelfde bewerking op symboolreeksen specificeren als de Turingmachine zelf.

Werkelijke Turing-volledigheid vereist dat een systeem tijdens het bewerken over willekeurig veel werkgeheugen kan beschikken. Informeel worden ook systemen die slechts een vaste hoeveelheid geheugen beschikbaar stellen wel Turing-volledig genoemd, als deze beperking in de simulatie geen rol speelt en als implementatiedetail kan worden beschouwd.

Voorbeelden[bewerken]

Het eerste voorbeeld van zo'n Turing-volledige machine zou de analytische machine van Charles Babbage zijn geweest, maar deze is nooit echt gebouwd. De eerste echte machine die, afgezien van haar eindige geheugen, Turing-volledig genoemd kon worden, was de Z3 van Konrad Zuse. Deze machine werd reeds in 1941 gebouwd, doch pas in 1998 is bewezen dat ze Turing-volledig was. De eerste machine waarvan men wist dat ze Turing-volledig was, was de ENIAC. Ook alle thuiscomputers zijn Turing-volledig.

Dat dit begrip een belangrijk begrip is voor de informatica kan ingezien worden door het feit dat elke (echt maakbare) computer die tot dusver ontworpen is, supercomputers en kwantumcomputer inbegrepen, door een Turingmachine geëmuleerd kan worden. Voor een computer die Turingvolledig is, geldt dit ook, in beginsel (afgezien van geheugenbeperkingen) kan een thuiscomputer elke berekening doen die een supercomputer ook kan doen. Uiteraard zal een thuiscomputer er véél langer over doen, en een equivalent programma voor een Turingmachine maken zal waarschijnlijk ontzettend veel moeilijker zijn, maar het is niet onmogelijk.

Theoretisch gezien bestaan er modellen van computers die krachtiger zijn dan de Turingmachine, bijvoorbeeld een Orakelmachine, die elk beslissingsprobleem kan beantwoorden (zoals een orakel dat doet, door te 'gokken'), dus ook problemen die formeel onbeslisbaar zijn, zoals het haltingprobleem. Deze machines, of equivalente machines, zijn echter fysiek niet te realiseren. Dit heeft sommigen de hypothese doen opwerpen dat het universum zelf berekenbaar is, dus gesimuleerd zou kunnen worden op een Turingmachine. Dit zou betekenen dat een computer krachtiger dan de Turingmachine niet mogelijk is, aangezien onder deze hypothese een Turingmachine deze computer zou kunnen emuleren.

Voorbeelden van Turing(on)volledigheid[bewerken]

Alle veelgebruikte programmeertalen zijn Turing-volledig. Dit zijn imperatieve talen zoals C, object-georiënteerde talen zoals Java, maar ook functionele talen zoals LISP en Haskell en logische programmeertalen zoals Prolog. Dit betekent dus bijvoorbeeld dat voor elk programma dat je in Prolog kunt schrijven je een equivalent programma in C kunt schrijven, en omgekeerd. Equivalent moet hier strikt formeel opgevat worden, de manier waarop het resultaat berekend wordt kan volledig anders zijn.

Ook heel basale talen, zoals de ongetypeerde lambdacalculus, die maar een paar constructies kennen, zijn Turing-volledig. Echter, sommige getypeerde lambda-calculi, zoals de tweede orde lambda calculus, zijn niet Turing-volledig.

Het is zelfs vrij moeilijk om voorbeelden van talen te vinden die niet Turing-volledig zijn, aangezien deze talen vrij beperkt zijn. Een voorbeeld is echter een spreadsheet zonder wederzijdse afhankelijkheden (dus lussen) in de cellen. Ook reguliere expressies zijn niet Turing-volledig, aangezien deze gemodelleerd kunnen worden door eindige automaten, apparaten met hooguit eindig veel geheugen.

Kenmerken van Turingvolledigheid[bewerken]

Een belangrijk resultaat uit de berekenbaarheidstheorie is, dat het in het algemeen onmogelijk is om te zeggen of een programma dat geschreven is in een Turing-volledige taal een keer ophoudt, of dat het oneindig blijft doorrekenen, het zogenaamde haltingprobleem. Methodes die ervoor zorgen dat je er zeker van kunt zijn dat een programma stopt, zoals het programma stoppen na een vaste tijd, of de mogelijkheden om oneindige lussen te maken te beperken, leiden dan ook tot Turing-onvolledige talen.

Een gerelateerd resultaat is dan ook dat er problemen zijn die een Turing-volledige taal wel kan oplossen, maar die niet opgelost kunnen worden door een taal met eindige herhalingsmogelijkheden — talen die dus garanderen dat programma's stoppen.

Zie ook[bewerken]