In this series, I want to show you how to create a simple console-based Turing machine in Python. You can check out the full source code on https://github.com/phillikus/turing_machine.
In this part, I will explain the fundamental theory behind Turing machines and set up the project based on that.
Requirements
- Basic knowledge of Python
- Fundamentals of theoretical computer science
What Is a Turing Machine?
A Turing machine is a mathematical model of computation that reads and writes symbols of a tape based on a table rules. Each Turing machine can be defined by a list of states and a list of transitions. Based on a start state (s0), the Turing machine works its way through all the states until it reaches a final state (sf). If no transition leads to the final state, the Turing machine will run ‘forever’ and eventually run into errors.
A transition is defined by the current state, the read symbol at the current position on the tape, the next state and the next symbol that must be written to the tape. Additionally, it contains a direction to determine whether the head of the tape should move the left, right or not at all. To visualize this process, let’s take a look at a very simple Turing machine that increments the value from the initial tape by one.
Unary Increment
To keep it simple, we will start with a unary Turing machine. A one is represented by a ‘|’. So, a Turing machine that contains the number 3 would look like this:
$|||#
The $ represents the starting point of our Turing machine and # represents the end. After the Increment is complete, we expect the final tape to look like this:
$||||#
To reach that final state, our Turing machine simply has to read through all the ‘|’ and append a single ‘|’.
This can be represented by three states s0, s1 and sf with the following transitions:
(s0, ‘$’, s1, ‘$’, Right)
(s1, ‘|’, s1, ‘|’, Right)
(s1, ‘#’, sf, ‘|’, Neutral)
which can also be represented with the following state transition diagram:
We start in state s0 where we expect to read a ‘$’. Then we switch to state s1 and write back that ‘$’. Then, we move the head one character to the right.
In state s1, as long as we read a ‘|’, we stay in state s1 and write back that ‘|’. This way, we will move all the way to the right end of the tape.
Finally, when we encounter an “#”, we write a ‘|’ and go to the final state sf. Since we are done, there is no reason to move the head at this point.
Project Structure
While this is a very simple Turing machine, we can use the same model to create machines of any complexity. With that knowledge, we are now ready to lay out the basic structure of our project. To represent the entire Turing machine, we will need one class, a class for the states and transitions as well as the tape.
Additionally, we need an enumeration to represent the three directions in which we can move the head of the Turing machine: Left, Right and Neutral (no movement).
Finally, we need one class that combines all these components and uses them to process the Turing machine. Adding a file for each of these classes, I ended up with the following structure:
This concludes part 1 of this series. We have now a basic understanding of Turing machines and have set-up the project. With that, it’s now time to get coding! In the next article of this series, we will implement the code to make our Turing machine work and feed it with the Increment machine defined above.
Thank you for reading this article. :) If you have any questions, problems or feedback, please let me know in the comments.
