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:
This class contains only an enum that will be used to move the head of the tape. Therefore, it’s 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:
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:
__init__ method takes in a
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 put’s them in the tape, as long as they are inside the alphabet. Finally, it turns them into a list.
_tape with double and single underscore respectiveley, to mark them as protected and prevent consumers from using it.
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
_remove_trailing_sharps methods, which will be used to return the current state of the tape.
move_head method takes in a
Direction and moves the head of the tape in that direction.
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:
Empty. The Turing machine starts at the
Start-state and ends when it reaches the
Final state. All
Empty states lie in between.
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:
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)
__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:
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 it’s
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.