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:

f1

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
         a = self.tape[self.head]
         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.

p4

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'
program = open('program.txt').read()
tm = TuringMachine(program, input)
tm.run()
# 10010 H

The following animation shows how the binary numbers are added using the TM simulator.

badd

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:

p5
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.

b2u

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:

p6

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.

u2b

 

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

p1

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.

double

 

5. Simulating the 4-state Busy Beaver with TM


The following figure shows the program to be run

p3

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.
bb

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.

p2

The following animation shows the result of running the program on the TM simulator with a palindrome.

palint

The following animation shows the result of running the program on the TM simulator with a non-palindrome.

palinf

 

 

3 thoughts on “Simulating a Turing Machine with Python and executing programs on it

  1. Pingback: Simulating a #TuringMachine with #Python and executing programs on … | Dr. Roy Schestowitz (罗伊)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s