In the last part, we covered the theory of Turing machines and created the basic project structure and classes. Now we are going to implement those classes one by one.
direction.py
This class contains only an enum that will be used to move the head of the tape. Therefore, its implementation is very straightforward:
from enum import Enum
class Direction(Enum):
Left = 1
Right = 2
Neutral = 3
We will use this enum in the tape.py class, so let’s jump right into it:
tape.py
from direction import Direction
class Tape:
def __init__(self, word, alphabet):
self.alphabet = alphabet + "$#"
self.head_position = 0
self.__init_tape(word)
def __init_tape(self, word):
tape = "$";
for char in (c for c in word if c in self.alphabet):
tape += char
tape += "#";
self._tape = list(tape)
def write(self, character):
if self.head_position < 1 or character not in self.alphabet:
return
self._tape[self.head_position] = character
last_item_index = len(self._tape) - 1
if self.head_position == last_item_index:
self._tape += '#'
def read(self):
if self.head_position < 0 or self.head_position > len(self._tape) - 1:
raise Exception('Trying to read character at invalid position: ' + self.head_position)
return self._tape[self.head_position]
def get_tape(self):
self._remove_trailing_sharps()
return ''.join(self._tape)
def move_head(self, direction):
if direction == Direction.Right:
self.head_position += 1
elif direction == Direction.Left:
self.head_position -= 1
if self.head_position > len(self._tape) - 1:
self._tape += '#'
if self.head_position < 0:
self.head_position = 0
def get_length(self):
return len(self._tape)
def _remove_trailing_sharps(self):
for i in range(len(self._tape) - 1, 1, -1):
if self._tape[i] == '#' and self._tape[i-1] == '#':
del self._tape[-1:]
else:
break
Let’s walk through it one by one:
The __init__ method takes in a word and alphabet. At first, we add the $ and # characters to the alphabet, as these represent the initial and last character on the tape. Then we initialize a head_position member variable and set it to 0, the start of the tape. Finally, we call the __init_tape method, which takes all characters from the word and puts them in the tape, as long as they are inside the alphabet. Finally, it turns them into a list.
I marked __init_tape and _tape with double and single underscore respectively, to mark them as protected and prevent consumers from using it.
The write and read methods simply read or write a character from/to the tape. Note how we add an additional # when we write a char at the end of the tape. This allows us to increase the size of the tape as we desire.
Next, we have the get_tape and _remove_trailing_sharps methods, which will be used to return the current state of the tape.
Finally, the move_head method takes in a Direction and moves the head of the tape in that direction.
state.py
This component contains another enum, which represents the type of the state as well as the State class itself:
from enum import Enum
class StateType(Enum):
Start = 1
Final = 2
Empty = 3
class State:
def __init__(self, id, state_type):
self.id = id
self.type = state_type
The class itself contains only an id and a state-type, which will later be evaluated by the turing-machine. The only states we will need are: Start, Final and Empty. The Turing machine starts at the Start-state and ends when it reaches the Final state. All Empty states lie in between.
transition.py
In the same manner, we can now define the Transition class. It contains the current and next state as well as the current and next char to write to the tape:
from state import State
class Transition:
def __init__(self, current_state, current_char, new_state, new_char, direction):
self.current_state = current_state
self.current_char = current_char
self.new_state = new_state
self.new_char = new_char
self.direction = direction
With all the basic classes set up, we can now go to the actual implementation of the Turing machine.
turing_machine.py
This class combines all the classes we defined before and uses them to move through the states of the Turing machine until it reaches the final state:
from state import StateType
class TuringMachine:
def __init__(self, states, transitions, tape):
self.states = states
self.start_state = self.get_start_state()
self.transitions = transitions
self.tape = tape
def get_tape(self):
return self.tape.get_tape()
def get_start_state(self):
return next(state for state in self.states if state.type == StateType.Start)
def process(self, verbose=False):
current_state = self.start_state
while current_state.type != StateType.Final:
current_char = self.tape.read()
state_id = current_state.id
transition = next(t for t in self.transitions
if t.current_state == state_id
and t.current_char == current_char)
current_state = next(state for state in self.states if state.id == transition.new_state)
self.tape.write(transition.new_char)
self.tape.move_head(transition.direction)
The __init__ method takes a list of states, a list of transitions and a tape.
Let’s take a closer look at the process method, which contains the main logic of the Turing machine.
current_state = self.start_state
First, we initialize a current_state variable and set it to the start state of the Turing machine. With each iteration, we will try to find the next state of the Turing machine and assign it to this variable. When we reach the final state, the process method is done.
while current_state.type != StateType.Final:
current_char = self.tape.read()
state_id = current_state.id
Inside this loop, we first get the current character and state-id from the tape and the current state. Then, we use both of them to find the first transition that matches these values:
transition = next(t for t in self.transitions if t.current_state == state_id and t.current_char == current_char)
Since this transition contains the next state of the Turing machine, we will override the current_state variable with it:
current_state = next(state for state in self.states if state.id == transition.new_state)
Finally, we have to write the new character from the transition to the tape and move the tape in the direction defined by the transition:
self.tape.write(transition.new_char)
self.tape.move_head(transition.direction)
This is all we have to do to push the Turing machine to the next state. This step will be repeated until the Turing machine reaches the Final state.
Testing the Turing Machine
Since this whole process may seem a little bit abstract, let’s try to visualize it, by testing our machine. To keep it simple, I decided to start with the Increment Turing machine I showed you in the last part. To create such a machine, I added a new file console_client.py and put the following code in it:
from turing_machine import TuringMachine
from state import State, StateType
from transition import Transition
from direction import Direction
from tape import Tape
tape = Tape('|||', '|')
states = [
State("s0", StateType.Start),
State("s1", StateType.Empty),
State("sf", StateType.Final)
]
transitions = [
Transition("s0", "$", "s1", "$", Direction.Right),
Transition("s1", "|", "s1", "|", Direction.Right),
Transition("s1", "#", "sf", "|", Direction.Neutral)
]
tm = TuringMachine(states, transitions, tape)
tm.process();
print(tm.get_tape())
To catch up with the definition of the Turing machine, go back to part 1.
I initialized the tape with the value ‘|||’ and added ‘|’ as only valid character (beside $ and #). Then I defined the states and transitions and used them to instantiate the TuringMachine. Calling its process method should then go through all these states and transitions and write a final ‘|’ at the end of the tape.
If we have done everything correctly, the final print statement should display: $||||#.
That’s it for part 2! I hope you enjoyed this article. In the final part, we will add some more complicated Turing machines and extend the logging, which will allow us to see the result of each step the Turing machine takes.
Thank you for reading this article. :) If you have any questions, problems or feedback, please let me know in the comments.
