De Turingmachine is 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 hypothetische machine bewerkt een oneindig lange band (zowel naar links als naar rechts). Deze band is verdeeld in vakjes waarin een symbool kan geschreven worden. Initieel is de band leeg. Om de band te bewerken gebruikt de Turingmachine toestanden. Sommige van die toestanden zijn die aanvaardende toestanden. Als de Turingmachine in een aanvaardende toestand terechtkomt stopt ze en aanvaard ze (geeft als het ware true terug). Om te wisselen tussen de toestanden maakt de machine gebruik van een transitie functie \(\delta\). Als \(\delta(q_0,t_0) = (q_1,t_1, \rightarrow)\) wilt dat zeggen dat als de Turingmachine zich in toestand \(q_0\) bevind en het symbool \(t_0\) onder de kop van de Turingmachine staat, dat de Turingmachine de waarde onder de kop veranderd door \(t_1\) en vervolgens naar rechts opschuift op de band en de toestand \(q_1\) aanneemt. Als \(\delta(q_0,t_0) = (q_1,t_1, \leftarrow)\) gebeurt hetzelfde maar dan schuift de Turingmachine op naar links in plaats van naar rechts.
Turingmachines kunnen worden gebruikt om waarden te berekenen. Hiervoor wordt de waarde die moet worden verwerkt op de band gezet na de kop van de Turingmachine en wordt de waarde na de kop eens de Turingmachine stopt uitgelezen als antwoord.
We kunnen de transitiefunctie beschrijven als een prolog predicaat transition/5. Zodat
transition(CState, CTape, NState, NTape, >) als en slechts als \(\delta(\texttt{CState},\texttt{CTape}) = (\texttt{NState},\texttt{NTape}, \rightarrow)\) entransition(CState, CTape, NState, NTape, <) als en slechts als \(\delta(\texttt{CState},\texttt{CTape}) = (\texttt{NState},\texttt{NTape}, \leftarrow)\)Aanvaardenden toestanden kunnen worden aangegeven met accepting(State). Toestanden waarin de Turingmachine wel stopt, maar niet aanvaard kunnen worden aangegeven met halting(State).
Het volgende is bijvoorbeeld een programma op 1 op te tellen bij een binair getal dat op de band staat.
accepting(qh). % qh is een accepting toestand
% huidige waarde nieuwe schrijf
% toestand band toestand op band beweging
transition( qs , blank , qs , blank , > ).
transition( qs , C , q0 , C , > ) :-C\==blank.
transition( q0 , C , q0 , C , > ) :-C\==blank.
transition( q0 , blank , q1 , blank , < ).
transition( q1 , 1 , q1 , 0 , < ).
transition( q1 , 0 , q2 , 1 , < ).
transition( q2 , C , q2 , C , < ) :-C\==blank.
transition( q2 , blank , qh , blank , > ).
Schrijf een predicaat turing(+State, +Input, -Output) die Output unificeert met
ok(Tape) als de TM gestart op ([], blank, Input) stopt in een accepting/1 toestand met Tape de inhoud vanaf de positie van de kop tot het meest rechtse gebruikte vak.fail(Tape) als de TM gestart op ([], blank, Input) stopt in een halting/1 toestand met Tape de inhoud vanaf de positie van de kop tot het meest rechtse gebruikte vak.Als de TM vastloopt (omdat er geen regels meer toepasbaar zijn bijvoorbeeld) moet het predicaat falen.
Gebruik een hulppredicaat turing(State, Pre, CTape, Post, Output) die waar is als een Turingmachine die zich in de toestand State bevind en wiens band wordt beschreven door Pre, CTape, Post een output Output geeft (zoals hierboven beschreven). Hierbij wordt de band beschreven als twee stapels. Pre is de stapel van elementen voor de kop van de Turingmachine, in omgekeerde volgorde, CTape is de huidige waarde onder de het kop en Post is de stapel van elementen achter de Turingmachine. Vakken die leeg zijn worden aangeduid met het atoom blank.
qs
V
| | | 0 | 9 | 8 | 7 | 2 | 1 | 9 | | | |
State = qs
Pre = [9,0,blank,blank]
Cur = 8
Post = [7,2,1,9,blank,blank,blank]
Na het toepassen van de transitie transition(qs,8,q0,1,>) ziet de band er zo uit:
q0
V
| | | 0 | 9 | 1 | 7 | 2 | 1 | 9 | | | |
State = q0
Pre = [1,9,0,blank,blank]
Cur = 7
Post = [2,1,9,blank,blank,blank]
Houd er rekening mee dat de band van een turingmachine oneindig lang is. Als 1 van de stapels leeg is moet je emuleren dat er toch nog blank staat. Je mag er voor deze oefening van uitgaan dat de turingmachine deterministisch is (er is altijd hoogstens 1 transisie mogelijk).
In de literatuur is er een Turingmachine beschreven die stopt in een aanvaardende toestand als de Riemanhypothese niet waar is. Als je die turringmachien herschrijft en laat uitvoeren met jou interpreter wordt je mischien dollar milionair, het is immers een Millenniumprijsprobleem1.