Intro

A Turing machine (TM) is a mathematical model of computation that defines an abstract machine, which manipulates symbols on an infinitely long strip of tape according to a table of rules. Despite the model’s simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm’s logic can be constructed.

Actions of the turing machine in a certain state \(q_0\) always go according the to the following schedule:

1. If \(q_0\) is an accepting or halting state stop and accept or reject
2. Read the current value under the head of the TM and call it \(t_0\)
3. Lookup the current state and the value on the tape in the table of rules (described by the function \(\delta\))
   • if \(\delta(q_0,t_0) = (q_1,t_1, \rightarrow)\),
     • write \(t_1\) on the tape at the current position
     • Change the current state to \(q_1\)
     • Move to the right on the tape
     • repeat at 1
   • if \(\delta(q_0,t_0) = (q_1,t_1, \leftarrow)\),
     • write \(t_1\) on the tape at the current position
     • Change the current state to \(q_1\)
     • Move to the left on the tape
     • repeat at 1
   • else fail

turing machines that compute values

We can also use a TM to compute functions on values. To do this we initialise the tape with the input value to our function. Then we execute the machine and look at what remains on the tape.

Turingmachine in Prolog

Table of rules

We can tranform the table of rules into a prolog predicate transition/5.

• transition(CState, CTape, NState, NTape, >) if and only if \(\delta(\texttt{CState},\texttt{CTape}) = (\texttt{NState},\texttt{NTape}, \rightarrow)\) en
• transition(CState, CTape, NState, NTape, <) if and only if \(\delta(\texttt{CState},\texttt{CTape}) = (\texttt{NState},\texttt{NTape}, \leftarrow)\)

Accepting and rejecting states

If a TM arrives at an accepting state (indicated by accepting(State)), it stops executing and “returns true”. On the other hand, if a halting state (halting(State)) is reached the input is rejected (return false).

Examle

accepting(qh). % qh is een accepting toestand

%           current     value       new      write on 
%            state       tape      state     tape      movement
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  , >  ).

Real Turingmachines

Exersise

Write a predicate turing(+State, +Input, -Output) that unifies Output with

• ok(Tape) if the TM started in ([], blank, Input) stops in a accepting/1 state with Tape being the content of the tape starting from the head.
• fail(Tape) if the TM started in ([], blank, Input) stops in a halting/1 state with Tape being the content of the tape starting from the head.

If the TM cannot make a further move it is considered stuck, in this case the predicate should fail.

Use a helper predicate turing(State, Pre, CTape, Post, Output) that is the if the Turing machine started in state State on the tape described by Pre, CTape, Post gives the output Output (as described above). The tape is represented by two stacks. Pre is a stack of elements before the head, with the one on top being the nearest to the head. Cur is the tape symbol currently under the TM’s head. Post is a stack of elements after the head, again with the closes elements on top. It the TM reaches a place that is not yet defined (the stack is empty) the value of blank should be inserted.

This is an example

                 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]

After applying transition(qs,8,q0,1,>) the tape looks like this:

                     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]

For this exercise, you may assume that the the given Turing machine is deterministic (at most one transition applies to a state).

Epilog

in the literature, there is a Turing machine that stops if the Rieman Hypothesis is false. Using the interpreter you write here you may become a dollar millionaire because proving the Rieman hypothesis wrong (or true) is a Millennium problem¹.

Yedidia, Adam, and Scott Aaronson. “A relatively small Turingmachine whose behavior is independent of set theory.” arXiv preprint arXiv:1605.04343 (2016).²