# Simulating a Turing Machine with Python and executing programs on it

In this article, we shall implement a basic version of a Turing Machine in python and write a few simple programs to execute them on the Turing machine.  This article is inspired by the edX / MITx course Paradox and Infinity and few of the programs to be executed on the (simulated) Turing machine are taken from the course. Also, some programs are from this Cambridge tutorial.

### A few Definitions

Let’s start by defining a Turing machine (originally invented by Alan Turing) formally, as is shown in the following figure: In this article, we shall assume that the tape alphabet can contain only the symbols  {0,1,⊔}, the head on the Turing machine moves in left (L) / right (R) direction (D) or doesn’t move (*), upon reading a symbol on the tape (i.,e., D can be one of {L,R,*}). Also, given a program along with a valid input, the Turing machine just halts (goes to the state halt) after writing the desired output on its tape.

### The python implementation for simulating a Turing Machine

The following python code shows a very simple implementation of a Turing machine.  It accepts a program as a string, with each transition function defined on a new line. The state halt is denoted by H.


N = 1000 # tape length, initialize to a large value

class TuringMachine:

'''
initialize the Turing Machine, read the program and input
'''
def __init__(self, program, input, state=0):
self.trf = {}
self.state = str(state)
self.tape = ''.join(['_']*N)
self.head = N // 2   # head is positioned in the middle
self.tape = self.tape[:self.head] + input + self.tape[self.head:]
for line in program.splitlines():
s, a, r, d, s1 = line.split(' ')
self.trf[s,a] = (r, d, s1)

'''
step through a program
'''
def step(self):
if self.state != 'H':
# assert self.head >= 0 and self.head < len(self.tape) here
action = self.trf.get((self.state, a))
if action:
r, d, s1 = action
self.tape = self.tape[:self.head] + r + self.tape[self.head+1:]
if d != '*':
self.head = self.head + (1 if d == 'r' else -1)
self.state = s1
print(self.tape.replace('_', ''), self.state)

'''
run a program
'''
def run(self, max_iter=9999):
iter = 0
while self.state != 'H' and iter < max_iter: # prevent infinite loop
self.step()
iter += 1
print(self.tape.replace('_', ''), self.state)



In the next section we shall show how a program on this Turing Machine will look like and how to run such a program, by instantiating the above class. We shall demonstrate with a few programs.

### 1. Binary Addition with Turing Machine

The following figure shows how to perform binary addition with a Turing machine, where the binary numbers to be added are input to the Turing machine and are separated by a single blank. The TM header is assumed to be positioned at the leftmost position of the first number, in the very beginning. The program is loaded as a text file (program.txt) that looks like the following (here each line represents a transition function of the form 𝛿(𝑝,𝑋)=(𝑞,𝑌,D), where the 5 tuples are strictly in the order p, X, Y, D, q (the character _ represents a blank symbol on the tape):

0 0 0 r 0
0 1 1 r 0
0 _ _ r 1
1 0 0 r 1
1 1 1 r 1
1 _ _ l 2
2 0 1 l 2
2 1 0 l 3
2 _ _ r 5
3 0 0 l 3
3 1 1 l 3
3 _ _ l 4
4 0 1 r 0
4 1 0 l 4
4 _ 1 r 0
5 1 _ r 5
5 _ _ * H

Given the two binary numbers, the Turing Machine

• uses the second number as a counter
• decrements the second number by one
• increments the first number by one

till the second number becomes 0.

The following code shows how the above program can be run to add two input binary numbers 1101 (decimal 13) and 101 (decimal 5) to output the binary number 10010 (decimal 18). The final state of the machine is H (halt), as expected.

input = '1101_101'
tm = TuringMachine(program, input)
tm.run()
# 10010 H


The following animation shows how the binary numbers are added using the TM simulator. ### 2. Converting a Binary to a Unary number with TM

Let’s assume the TM tape contains a binary representation of a number n (n> 0) as a sequence of zeros and ones, and is otherwise blank. The reader positioned at the left-most member of the sequence. The following figure shows the program that replaces the original sequence with a sequence of n ones, where the original sequence names n in binary notation: The following animation shows the result of running the program on the TM simulator, with the input 1010, the output obtained is a sequence of 10 ones. ### 3. Converting a Unary to a Binary number with TM

Let’s assume the TM tape contains a sequence of n ones (n> 0) and is otherwise blank. The reader positioned at the left-most member of the sequence. The following TM  program replaces the sequence of n ones, with a sequence of zeroes and ones that names n in binary notation: The following animation shows the result of running the program on the TM simulator, with the input 11111111111 (eleven ones), the output obtained is the binary representation of 11. ### 4. Doubling the length of a sequence with TM

The following figure shows the program to be run to double the length of a sequence of ones, input to the TM The following animation shows the result of running the program on the TM simulator, starting with five ones as input, obtaining ten ones on the tape as output. ### 5. Simulating the 4-state Busy Beaver with TM

The following figure shows the program to be run The following animation shows the result of running the program on the TM simulator, as expected it outputs 13 ones on the tapes and halts in 107 steps. ### 6. Detecting a Palindrome with TM

The following program checks a string of symbols on the tape and returns a 1 if it is a palindrome and a 0 if it is not. The following animation shows the result of running the program on the TM simulator with a palindrome. The following animation shows the result of running the program on the TM simulator with a non-palindrome. ## 3 thoughts on “Simulating a Turing Machine with Python and executing programs on it”

1. 360DigiTMGIN

I like viewing web sites which comprehend the price of delivering the excellent useful resource free of charge. I truly adored reading your posting. Thank you!
360DigiTMG

Like

2. Aaron Stachniw

thank you

Like