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

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.

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

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

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

LikeLike

thank you

LikeLike