## Turing Machine

Just to let you know straight-away: The Turing machine is not a machine. It is a mathematical model, which was formulated by the English mathematician Alan Turing in 1936. It's a very simple model of a computer, yet it has the complete computing capability of a general purpose computer. The Turing machine (TM) serves two needs in theoretical computer science:

- The class of languages defined by a TM, i.e. structured or recursively enumerable languages
- The class of functions a TM is capable to compute, i.e. the partial recursive functions

## Formal Definition of a Turing machine

A deterministic Turing machine can be defined as a 7-tupleM = (Q, Σ, Γ, δ, b, q

_{0}, q

_{f})

with

- Q is a finite, non-empty set of states
- Γ is a finite, non-empty set of the tape alphabet
- Σ is the set of input symbols with Σ ⊂ Γ
- δ is a partially defined function, the transition function:

δ : (Q \ {q_{f}}) x Γ → Q x Γ x {L,N,R} - b ∈ &Gamma \ Σ is the blank symbol
- q
_{0}∈ Q is the initial state - q
_{f}∈ Q is the set of accepting or final states

### Example: Binary Complement function

Let's define a Turing machine, which complements a binary input on the tape, i.e. an input "1100111" e.g. will be turned into "0011000".Σ = {0, 1}

Q = {init, final}

q

_{0}= init

q

_{f}= final

Function Definition | Description |
---|---|

δ(init,0) = (init, 1, R) | If the machine is in state "init" and a 0 is read by the head, a 1 will be written, the state will change to "init" (so actually, it will not change) and the head will be moved one field to the right. |

δ(init,1) = (init, 0, R) | If the machine is in state "init" and a 1 is read by the head, a 0 will be written, the state will change to "init" (so actually, it will not change) and the head will be moved one field to the right. |

δ(init,b) = (final, b, N) | If a blank ("b"), defining the end of the input string, is read, the TM reaches the final state "final" and halts. |

## Implementation of a Turing machine in Python

We implement a Turing Machine in Python as a class. We define another class for the read/write tape of the Turing Machine. The core of the tape inside the class Tape is a dictionary, which contains the entries of the tape. This way, we can have negative indices. A Python list is not a convenient data structure, because Python lists are bounded on one side, i.e. bounded by 0.We define the method __str__(self) for the class Tape. __str__(self) is called by the built-in str() function. The print function uses also the str function to calculate the "informal" string representation of an object, in our case the tape of the TM. The method get_tape() of our class TuringMachine makes use of the str representation returned by __str__.

With the aid of the method __getitem__(), we provide a reading access to the tape via indices. The definition of the method __setitem__() allows a writing access as well, as we can see e.g. in the statement

`self.__tape[self.__head_position] = y[1]`

of our class TuringMachine implementation.

The class TuringMachine:

We define the method __str__(self), which is called by the str() built-in function and by the print statement to compute the "informal" string representation of an object, in our case the string representation of a tape.

class Tape(object): blank_symbol = " " def __init__(self, tape_string = ""): self.__tape = dict((enumerate(tape_string))) # last line is equivalent to the following three lines: #self.__tape = {} #for i in range(len(tape_string)): # self.__tape[i] = input[i] def __str__(self): s = "" min_used_index = min(self.__tape.keys()) max_used_index = max(self.__tape.keys()) for i in range(min_used_index, max_used_index): s += self.__tape[i] return s def __getitem__(self,index): if index in self.__tape: return self.__tape[index] else: return Tape.blank_symbol def __setitem__(self, pos, char): self.__tape[pos] = char class TuringMachine(object): def __init__(self, tape = "", blank_symbol = " ", initial_state = "", final_states = None, transition_function = None): self.__tape = Tape(tape) self.__head_position = 0 self.__blank_symbol = blank_symbol self.__current_state = initial_state if transition_function == None: self.__transition_function = {} else: self.__transition_function = transition_function if final_states == None: self.__final_states = set() else: self.__final_states = set(final_states) def get_tape(self): return str(self.__tape) def step(self): char_under_head = self.__tape[self.__head_position] x = (self.__current_state, char_under_head) if x in self.__transition_function: y = self.__transition_function[x] self.__tape[self.__head_position] = y[1] if y[2] == "R": self.__head_position += 1 elif y[2] == "L": self.__head_position -= 1 self.__current_state = y[0] def final(self): if self.__current_state in self.__final_states: return True else: return FalseUsing the TuringMachine class:

from turing_machine import TuringMachine initial_state = "init", accepting_states = ["final"], transition_function = {("init","0"):("init", "1", "R"), ("init","1"):("init", "0", "R"), ("init"," "):("final"," ", "N"), } final_states = {"final"} t = TuringMachine("010011 ", initial_state = "init", final_states = final_states, transition_function=transition_function) print("Input on Tape:\n" + t.get_tape()) while not t.final(): t.step() print("Result of the Turing machine calculation:") print(t.get_tape())

The previous program prints the following results:

Input on Tape: 010011 Result of the Turing machine calculation: 101100