Computers, Science, & Computer Science

Turing Machine Simulator in Python with curses screen display of tape’s progress

By AdamKolany (Own work) [CC-BY-SA-3.0 (http://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia CommonsThe program reads the TM from file. The file contains a binary adder. I'll add some more commentary in due course.
'''     Turing Machine Simulator in Python

        Uses curses to show the tape's progress.
        The TM is read from a file. Tape is read from data (just below).
'''
import fileinput
import time
import curses
stdscr = curses.initscr()
curses.cbreak()
stdscr.keypad(1)
curses.curs_set(0)
tx=30;ty=10

data='_101_101_____________________________'

def showtape():
    i=0
    stdscr.addstr(ty-2,tx,'State:   ')
    stdscr.addstr(ty-2,tx,'State: ' + state)
    for e in tape:
        if i == pos:
            attr = curses.A_REVERSE
        else:
            attr = curses.A_NORMAL
        stdscr.addch(ty,tx+i,''.join(str(e)),attr)
        i=i+1
    stdscr.refresh()
    time.sleep(0.2)

try:
#       This tape is not infinite
    tape=[]
    for c in data:
        tape.append(c)

    code={}

    for line in fileinput.input("binadd.dat"):
        item=line.split()
        try:
            code[item[0]]
        except KeyError,e:
            code[item[0]]={}
        code[item[0]][item[1]]=item[2],item[3],item[4]

    pos=1
    state='0'
    showtape()
    stdscr.getch()
    while state != 'halt':
        sym=str(tape[pos])
        try:
            code[state][sym]

Turing machine:

Binary addition – add two binary numbers (separated by space). Assumes input of two binary numbers separated by a single space.

Syntax:

  • Each line should contain one tuple of the form ‘<current state> <current symbol> <new symbol> <direction> <new state>‘.
  • You can use any number or word for <current state> and <new state>, eg 0, a, state1. State labels are case-sensitive.
  • halt is the halting state. The machine starts in state 0.
  • You can use any character for <current symbol> and <new symbol>, or ‘_‘ to represent blank (space). Symbols are case-sensitive.
  • <direction> should be ‘l‘, ‘r‘ or ‘*‘, denoting ‘move left’, ‘move right’ or ‘do not move’, respectively.
  • Anything after a ‘;‘ is a comment and is ignored.

Also:

  • *‘ can be used in <current symbol> or <current state> to match any character or state.
  • *‘ can be used in <new symbol> or <new state> to mean ‘no change’.

1 _ _ r 1

0 * * r 0
1 _ _ l 2
1 * * r 1
2 0 _ l 3x
2 1 _ l 3y
2 _ _ l 7
3x _ _ l 4x
3x * * l 3x
3y _ _ l 4y
3y * * l 3y
4x 0 x r 0
4x 1 y r 0
4x _ x r 0
4x * * l 4x    ; skip the x/y's
4y 0 1 * 5
4y 1 0 l 4y
4y _ 1 * 5
4y * * l 4y    ; skip the x/y's
5 x x l 6
5 y y l 6
5 _ _ l 6
5 * * r 5
6 0 x r 0
6 1 y r 0
7 x 0 l 7
7 y 1 l 7
7 _ _ r halt
7 * * l 7

Leave a Reply

Your email address will not be published. Required fields are marked *