Python script to simulate Turing machine.

turing.py

"""
Turing machine implementation in Python

Example input:

(Machine to generate Collatz sequence)

0,I;1,I,R
1,I;2,I,L
2,I;3,I,R
2,_;4,_,L
3,I;2,I,R
3,_;12,_,L
4,I;4,I,L
4,>;5,>,R
5,I;6,>,R
5,_;11,_,L
6,I;7,_,N
7,_;8,_,R
8,I;9,_,L
8,_;10,_,L
9,_;7,I,R
10,I;10,I,L
10,_;10,_,L
10,>;5,I,R
11,I;11,I,L
11,>;0,>,R
12,I;12,I,L
12,>;13,>,R
13,I;14,_,R
13,_;21,_,N
14,I;14,I,R
14,_;15,_,R
15,I;15,I,R
15,_;16,_,N
16,_;17,I,R
17,_;18,I,R
18,_;19,I,N
19,I;19,I,L
19,_;20,_,L
20,I;20,I,L
20,_;13,_,R
21,_;22,_,R
21,I;27,I,N
22,_;22,_,R
22,I;23,I,N
23,I;23,I,R
23,_;24,_,L
24,I;25,_,L
25,I;25,I,L
25,>;21,>,R
25,_;26,I,L
26,_;26,_,L
26,>;21,>,R
27,I;27,I,R
27,_;28,I,N
28,I;28,I,L
28,>;0,>,R
q
IIIIII
"""

MAX_CELLS = 100

class Tape:
    def __init__(self):
        self.cells = '>' + '_' * (MAX_CELLS - 1)
        self.head = 1

    def move_left(self):
        self.head -= 1

    def move_right(self):
        self.head += 1

    def read(self):
        return self.cells[self.head]

    def write(self, c):
        self.cells = self.cells[0:self.head] + c + self.cells[self.head+1:]

    def clear(self):
        self.cells = '>' + '_' * (MAX_CELLS - 1)

    def set_input(self, input):
        self.clear()
        self.cells = self.cells[0] + input + self.cells[len(input)+1:]

    def display(self):
        print(self.cells[0:self.head] + '[' + self.cells[self.head] + ']' + self.cells[self.head+1:])

# TODO implement method to combine turing machines (?)
class TuringMachine:
    def __init__(self, q_0, delta):
        self.q = q_0
        self.delta = delta

    def step(self, tape):
        c = tape.read()

        if (self.q, c) not in self.delta:
            return True

        next = self.delta[(self.q, c)]
        self.q = next[0]
        tape.write(next[1])

        if next[2] == 'R':
            tape.move_right()
        elif next[2] == 'L':
            tape.move_left()

        return False

    def run(self, input):
        tape = Tape()
        halt = False

        tape.set_input(input)

        while not halt:
            # print(f'state={self.q}')
            tape.display()
            halt = self.step(tape)

if __name__ == '__main__':
    delta = {}

    while True:
        s = input('Enter transition (enter "q" when you are done): ')

        if s == 'q':
            break

        s = s.split(';')
        left = s[0].split(',')
        right = s[1].split(',')

        delta[(left[0], left[1])] = (right[0], right[1], right[2])

    tm = TuringMachine('0', delta)
    tm.run(input('Enter input: '))