Turingmachine

Principes

Computationele complexiteitstheorie

Modellen

Algoritme

Turingmachine

Lambdacalculus

Theorieën

Berekenbaarheid

Complexiteitsgraad

NP-volledig

In de informatica is de turingmachine een model van berekening en berekenbaarheid, ontwikkeld door de wiskundige Alan M. Turing in zijn beroemde artikel On computable numbers, with an application to the Entscheidungsproblem uit 1936-37.

De turingmachine is een eenvoudig mechanisme dat symbolen manipuleert. Ondanks deze eenvoud kan men hiermee de logica van elke mogelijke computer simuleren. Hoewel technisch realiseerbaar (zolang we willekeurige hoeveelheden band kunnen aanleveren), is deze machine niet bedoeld voor praktische computertechnologie, maar als een gedachte-experiment rond de limieten van mechanische berekeningen; ze wordt dus niet echt gebouwd.

De turingmachine is in principe een eenvoudig apparaat dat niet meer kan dan in één stap twee verschillende waarden aanpassen. Dit mechanisme is waarschijnlijk in staat om elke berekening die kan worden beschreven uit te voeren.

Een turingmachine bestaat uit twee onderdelen:

1. Een oneindige band, onderverdeeld in oneindig veel vakjes. Op elk moment is echter slechts een eindig deel van deze band beschreven.
2. Een apparaat met een lees/schrijfkop (een eindigetoestandsautomaat genaamd), dat de band kan lezen en erop kan schrijven.

Het actieve gedeelte van de machine is de eindigetoestandsautomaat. Deze automaat bevindt zich altijd in één bepaalde toestand. Deze toestand is er een uit een eindige verzameling van toestanden en de automaat kan, volgens bepaalde regels, overgaan van de ene toestand in de volgende.

De toestandsautomaat herhaalt (mogelijk een oneindig aantal malen) de volgende cyclus:

1. (in een toestand P): Lees wat er op de band staat op de plaats waar de lees/schrijfkop nu staat—noem dit bandkarakter K.
2. (nog steeds in toestand P): Zoek voor de combinatie (P, K) in de lijst van toestandsovergangen de combinatie (Q, K', D) op.
3. (nog steeds in toestand P): Schrijf K' op de band in plaats van K; verplaats het lees/schrijfhoofd één positie in de richting D (links of rechts); ga over naar toestand Q.
4. (in toestand Q):

Als Q een accepterende toestand is, dan is de berekening klaar en is het goed -- stop dan;

Als Q een afwijzende toestand is, dan kan er niet verder gerekend worden en is het verkeerd -- stop dan;

Q is niet accepterend of afwijzend -- begin weer vooraan.

Een berekening door een turingmachine begint altijd in een speciaal aangewezen toestand (de begintoestand) met de leeskop aan het begin van de band.

Als voorbeeld van een berekening tonen wij het optellen van twee getallen. Deze getallen staan op de band vanaf het begin (aan de linkerkant). Ieder getal is een serie van tekens '1' (bijvoorbeeld 3 is '111'). De twee afzonderlijke getallen worden gescheiden door een teken '0'. Verder staat er niets op de band ('lege' tekens). We beginnen in een begintoestand Qb. Een programma om deze getallen op te tellen ziet er als volgt uit:

Herhaal totdat we in accepterende of afwijzende toestand zijn:

1. Lees het karakter van de band op de plaats van de kop.
2. Is de toestand Qb:
   - Is dit karakter een '0' of '1', schrijf er dan een '1' voor in de plaats, verplaats de kop naar rechts en blijf in toestand Qb.
   - Is dit karakter 'leeg', schrijf er dan een 'leeg' karakter voor in de plaats, verplaats de kop naar links en ga naar toestand Q0.
   Is de toestand Q0:
   - Is dit karakter een '1', schrijf er dan een 'leeg' karakter voor in de plaats, verplaats de kop naar links en ga naar de accepterende toestand.
   - Is dit karakter een '0' of 'leeg', schrijf er dan een 'leeg' karakter voor in de plaats en ga naar de afwijzende toestand.

Zoals hieronder gedemonstreerd, is dit een correcte optelling.

Formeel gezien is een turingmachine TM een tupel van 7 elementen:

TM = ( Q {\displaystyle {\mathcal {Q}}} , Σ {\displaystyle \Sigma } , Γ {\displaystyle \Gamma } , δ {\displaystyle \delta } , q 0 {\displaystyle q_{0}} , q a {\displaystyle q_{a}} , q r {\displaystyle q_{r}} ) met

1. Q {\displaystyle {\mathcal {Q}}} een verzameling toestanden
2. Σ {\displaystyle \Sigma } een verzameling tekens, samen het invoeralfabet -- de invoer voor de berekening bestaat uit deze tekens
3. Γ = Σ ∪ { _ } {\displaystyle \Gamma =\Sigma \cup \{\_\}} het bandalfabet, alle tekens die op de band voor mogen komen -- dit is het invoeralfabet plus het speciale blanco karakter
4. δ : Q × Γ ↦ Q × Γ × { L , R } {\displaystyle \delta :{\mathcal {Q}}\times \Gamma \mapsto {\mathcal {Q}}\times \Gamma \times \{L,R\}} , de transitiefunctie die de toestandsovergangen, schrijfacties en kopbewegingen van de eindige automaat beschrijft
5. q 0 ∈ Q {\displaystyle q_{0}\in {\mathcal {Q}}} , de begintoestand
6. q a ∈ Q {\displaystyle q_{a}\in {\mathcal {Q}}} , de accepterende toestand
7. q r ∈ Q {\displaystyle q_{r}\in {\mathcal {Q}}} , de afwijzende toestand

Deze tupel vat de gehele automaat samen. De bewegingen van de eindige automaat zoals hierboven beschreven zijn vervat in de transitiefunctie δ {\displaystyle \delta } .

Deze automaat (de basisautomaat TM) is de simpelste TM-variant die er is. De band is standaard, enkelzijdig oneindig (vanaf de beginstand van de kop gaat de band maar in één richting oneindig door) en ze is deterministisch: voor ieder paar (toestand, bandsymbool) staat de transitie maar één triple toe als reactie van de automaat. Bestaat dit triple niet, dan loopt de automaat vast en heeft de berekening gefaald (als alternatief kan het ook verplicht zijn om ieder mogelijk paar op te nemen in de beschrijving, waarbij de "verkeerde" paren allemaal een toestandsovergang naar de afwijzende toestand veroorzaken).

Merk op dat de beschrijving geen informatie bevat over de beginpositie van de kop: deze is standaard aan het begin.

Als voorbeeld geven we de formalisering van onze "optellende automaat" van hierboven. Deze automaat is

T M + = {\displaystyle TM_{+}=}

( Q = { q b , q 0 , q a , q r } {\displaystyle {\mathcal {Q}}=\{q_{b},q_{0},q_{a},q_{r}\}} ,

Σ = { ′ 0 ′ , ′ 1 ′ } {\displaystyle \Sigma =\{'0','1'\}} ,

Γ = Σ ∪ { _ } {\displaystyle \Gamma =\Sigma \cup \{\_\}} ,

δ = ( q b , ′ 1 ′ ) ↦ ( q b , ′ 1 ′ , R ) ( q b , ′ 0 ′ ) ↦ ( q b , ′ 1 ′ , R ) ( q b , ′ _ ′ ) ↦ ( q 0 , ′ _ ′ , L ) ( q 0 , ′ 1 ′ ) ↦ ( q a , ′ _ ′ , L ) ( q 0 , ′ 0 ′ ) ↦ ( q r , ′ _ ′ , L ) ( q 0 , ′ _ ′ ) ↦ ( q r , ′ _ ′ , L ) {\displaystyle \delta ={\begin{matrix}(q_{b},'1')\mapsto (q_{b},'1',R)\\(q_{b},'0')\mapsto (q_{b},'1',R)\\(q_{b},'\_')\mapsto (q_{0},'\_',L)\\(q_{0},'1')\mapsto (q_{a},'\_',L)\\(q_{0},'0')\mapsto (q_{r},'\_',L)\\(q_{0},'\_')\mapsto (q_{r},'\_',L)\end{matrix}}}

q b {\displaystyle q_{b}} ,

q a {\displaystyle q_{a}} ,

q r {\displaystyle q_{r}} )

Merk op dat we nergens iets zeggen over wat er op de band moet staan of hoe of wat dit betekent (de machine begrijpt dat toch niet). Het enige dat van belang is voor de berekening is dat machine op een bepaalde manier reageert op de invoer, zolang deze invoer bestaat uit het invoeralfabet.

Al sinds de introductie van de turingmachine in 1936 bestaat het vermoeden (onbewijsbaar) dat de turingmachine een perfect model van berekenbaarheid is. Dat wil zeggen dat alles wat mechanisch berekend kan worden, berekend kan worden door een turingmachine - en wat niet berekend kan worden door een turingmachine, is niet mechanisch berekenbaar.

Mechanisch berekenbaar wordt normaal gesproken algoritmisch berekenbaar genoemd. Een probleem P is algoritmisch berekenbaar als er een algoritme, een stappenplan, bestaat dat het probleem oplost. Als er een turingmachine bestaat die een probleem oplost, dan bestaat een dergelijk algoritme. En omgekeerd.

Wat betekent het als een turingmachine een probleem oplost? Een probleem P wordt opgelost door een turingmachine als er een turingmachine TM is die P beslist: voor iedere instantie van P (iedere invoer die een voorbeeld is van probleem P), eindigt de TM in de accepterende of afwijzende toestand. Een dergelijke turingmachine TM heet een beslisser voor probleem P.

Daarnaast kennen we ook het concept van een herkenner voor P. Dit is een turingmachine die voor iedere positieve instantie van P in eindige tijd een accepterende toestand bereikt, maar voor elke negatieve instantie van P oneindig door blijft lopen. Dit noemen we over het algemeen geen oplossing van P.

Het bestaan van de turingmachine als model betekent dat wiskundigen kunnen nadenken over wat wel en niet berekenbaar is en hoe moeilijk klassen van problemen zijn om op te lossen (dit heet de complexiteit van een probleem).

Sinds 1936 is bewezen dat er problemen zijn die niet turing-oplosbaar zijn (er kan geen beslisser voor bestaan). Een voorbeeld is het halting problem of stopprobleem. Ook is bewezen dat er problemen zijn die niet turing-herkenbaar zijn (er kan geen herkenner voor zijn). Merk overigens op dat het feit dat een probleem niet turing-oplosbaar is, niet betekent dat instanties van dat probleem geen oplossingen hebben. Het betekent wel dat er geen turingmachine bestaat die elke instantie van het probleem kan oplossen.

Sinds 1936 hebben onderzoekers gekeken naar zeer veel verschillende varianten van het turingmodel van berekenbaarheid en naar wat hun aanpassingen betekenden voor de beslissingskracht van de nieuwe machines.

Voor de meeste varianten geldt dat de beslissingskracht niet verandert, omdat die varianten gesimuleerd kunnen worden op een "normale" turingmachine. Voorbeelden hiervan zijn turingmachines met meerdere banden (en koppen), turingmachines met één band met meerdere koppen (de parallelle machines, die gesimuleerd kunnen worden door iedere band te verplaatsen naar een eigen sectie van de band op een "normale" machine), machines met meerzijdig oneindige banden (zet de invoer in het midden van de "normale" band en laat de turingmachine beginnen met de band door te spoelen tot aan de invoer) en meer van die veranderingen.

Een variant die niet krachtiger is, maar wel een bijzonder effect heeft, is de non-deterministische turingmachine (NDTM). Hierbij verbindt de functie δ {\displaystyle \delta } aan ieder paar (toestand, teken) een of meer triples (toestand, teken, richting). Een NDTM kiest non-deterministisch een van de mogelijke opvolgertriples. Als er een mogelijkheid is een accepterende toestand te bereiken, wordt de invoer aangenomen, anders wordt de invoer afgewezen. Een NDTM kan altijd met een normale (deterministische) turingmachine gesimuleerd worden door alle mogelijke berekeningen van de NDTM na elkaar uit te voeren. Dit maakt deze machine wel veel langzamer dan de equivalente NDTM: eventueel heeft ze exponentieel keer meer stappen nodig. In sommige gevallen bestaan er echter wel equivalente deterministische turingmachines die minder dan exponentieel keer meer stappen nodig hebben. Of dat altijd het geval is, is niet bekend.

Een andere variant op de turingmachine is de enumerator: dit is een turingmachine met een "printer", die uitvoerstrings kan genereren als "bewijs" van berekening.

Een andere variant is die met een eindige band. Dit is nauwelijks een turingmachine meer: een dergelijke machine is volledig equivalent met een standaard eindigetoestandsautomaat.

Ten slotte is de variant opmerkenswaardig waarin de band weliswaar oneindig is, maar de machine alleen dat stuk mag gebruiken waar de invoer op stond. Deze machine beschrijft een klasse van problemen en formele talen bekend als de contextgevoelige talen.

De turingmachine heeft op twee manieren direct invloed gehad op de ontwikkeling van de computer en de informatica.

Om te beginnen was het turingmodel een inspiratie voor de wiskundige John von Neumann, die naar een manier zocht om de eerste computers bruikbaar te maken. Naar aanleiding van Turings machine ontwikkelde hij de Von Neumann-cyclus, een cyclus van handelingen die het mogelijk maakt een elektronisch apparaat precies te laten doen wat een turingmachine doet.

Daarnaast is de turingmachine het begin van een tak van wiskunde en informatica die vanuit formele specificaties van een probleem een programma afleidt dat het probleem oplost. Deze oplossingsstrategie (ontwikkeld door Tony Hoare, Edsger Dijkstra en anderen) gebruikt predicatencalculus om de stappen uit te rekenen die nodig zijn om een turingautomaat van de ene toestand naar een volgende te krijgen (maar niet om direct de stappen uit te rekenen die van de begintoestand tot de accepterende toestand leiden – dat probleem is niet turing-oplosbaar).

• Turingvolledigheid
• Church-Turing-hypothese