Click here to Skip to main content
15,868,052 members
Articles / Artificial Intelligence / Machine Learning

Creating a Turing Machine in Python – Part 1

Rate me:
Please Sign up or sign in to vote.
5.00/5 (9 votes)
3 Nov 2018CPOL3 min read 21.2K   24   4
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.

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:

Image 1

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:

Image 2

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.

This article is part of the series 'Creating a Turing Machine in Python View All

License

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


Written By
Software Developer (Senior)
Germany 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

 
QuestionWriting # in the example? Pin
Emile van Gerwen12-Nov-18 0:06
Emile van Gerwen12-Nov-18 0:06 
AnswerRe: Writing # in the example? Pin
Philipp_Engelmann22-Nov-18 7:37
Philipp_Engelmann22-Nov-18 7:37 
GeneralMy vote of 5 Pin
Hyland Computer Systems23-Dec-17 15:20
Hyland Computer Systems23-Dec-17 15:20 
GeneralRe: My vote of 5 Pin
Philipp_Engelmann23-Dec-17 21:20
Philipp_Engelmann23-Dec-17 21:20 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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