15,039,244 members
Articles / Artificial Intelligence / Machine Learning
Article
Posted 22 Dec 2017

11.1K views
14 bookmarked

Creating a Turing Machine in Python – Part 2

Rate me:
5.00/5 (8 votes)
22 Nov 2018CPOL4 min read
How to create a Turing machine in Python - Part 2

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:

Python
```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

Python
```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:

Python
```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:

Python
```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:

Python
```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.

Python
`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.

Python
```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:

Python
`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:

Python
`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:

Python
```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:

Python
```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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

 Software Developer (Senior) Germany
Hi there 🙂
My name is Philipp Engelmann, I work as a web developer at FIO SYSTEMS AG in Leipzig. I am interested in C#, Python, (REST-)API-Design, software architecture, algorithms and AI. Check out my blog at https://cheesyprogrammer.com/

Comments and Discussions

 First Prev Next
 A small typo... Galatei10-Nov-18 9:31 Galatei 10-Nov-18 9:31
 Re: A small typo... Philipp_Engelmann22-Nov-18 7:43 Philipp_Engelmann 22-Nov-18 7:43
 Last Visit: 31-Dec-99 18:00     Last Update: 25-Sep-21 15:39 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.