I’m not sure how I got to thinking about Turing Machines (TMs). I was going through some files recently and spent some time looking at busy-beaver.c (from 2017 according to the file date). It contains an implementation of a TM. But something else got me speculating about my own implementation; I just don’t recall what.
I decided to actually write it when it occurred to me that I could use a Python generator to implement the Turing Machine tape. Sadly, I didn’t think of it in time for the trilogy I just published about Python generators (part 1, part 2, part 3).
A Turing Machine is an abstraction of computation. It’s one of several; the lambda calculus is another. Any algorithm has a TM that performs it. Conversely, any TM is an algorithm. The caveat is that TMs are horrifically inefficient at performing algorithms.
The notion of a TM is fundamental to Computer Science and a deep topic I’ll only touch on shallowly here. A Turing Machine is a type of state machine, so it executes a “program” — table of state descriptions — based on symbols on an infinite tape, which is its “memory.” (For details on state machines, see my trilogy: part 1, part 2, part 3.)
The execution cycle of a TM is:
- Given the current state and tape value, find the program statement that matches.
- The program statement specifies what to write to the tape, which direction to move the tape, and which state to make the new current one.
- Go to #1
That’s all there is to a Turing Machine. Obviously, some of it needs explaining, but that’s the cycle. Given the current state, determine what to do, then go to the next state. Repeat.
The power comes from the “program” — the table of statements. Each statement has two identifying fields, current-state and current-tape-value, as well as three action fields, value-to-write, direction-to-move, next-state.
Here’s an example that’s based on the first one Alan Turing presented:
| State | Tape | Write | Move | Next |
|---|---|---|---|---|
| A | 0 | 0 | R | B |
| B | 0 | – | R | C |
| C | 0 | 1 | R | D |
| D | 0 | – | R | A |
It begins in state 0 (the first) and writes an infinite series to the tape: [0 1 0 1 0 1…] Note the blank spaces between the numbers. Those are part of the output (and a complication we’ll need to discuss later — it’s a three-symbol output, not just 1s and 0s).
To encode the program table, we’ll map letters to numbers. The move direction can be L (left), R (right) or 0 (don’t move; used in some formulations). We’ll encode those as -1, +1, and 0, respectively. Our table translates to Python as:
# Write (1020)* indefinitely
pgm1 = (
(0, 0, 1, +1, 1),
(1, 0, 0, +1, 2),
(2, 0, 2, +1, 3),
(3, 0, 0, +1, 0),
)
I used tuples rather than lists because the program is immutable, plus tuples are more lightweight.
Turing’s implementation allowed for blanks on the tape as distinct from 0. My implementation doesn’t do that, so rather than Turing’s [0, blank, 1, blank] pattern, I’m using [1, 0, 2, 0]. It’s effectively the same thing.
§ §
Here’s my first version of a Turing Machine:
def turing_machine (program, max_steps=32):
'''TM. program=(state,key,write,move,next)'''
outfmt = '%2d: S%d [%d] {%d,%s} (%s)'
def find_pgm_entry (_state, _curr):
for pe in program:
if (pe[0]==_state) and (pe[1]==_curr):
return pe
raise KeyError('No Program Entry!')
tape = [[0,0]]
tt = turing_tape(tape)
curr = tt.send(None) # start the tape
state = 0
watchdog = 1
while 0 <= state:
# Find appropriate program statement...
pe = find_pgm_entry(state,curr)
# Do some pretty-print stuff...
d = 'L' if pe[3]<0 else 'R'
x = 'HALT' if pe[4] < 0 else ('S%d' % pe[4])
out = (watchdog, state, curr, pe[2],d, x)
# Print current system state...
print(outfmt % out)
# ACTION: Write/move tape...
curr = tt.send(pe[2:4])
# Move to next state...
state = pe[4]
# Quit if we've been doing this too long...
watchdog += 1
if max_steps < watchdog:
break
# Trim unused tape ends...
out = [(t0,t1) for t0,t1 in tape if t1]
# Generate a nice print string...
ps0 = 'HALT' if state < 0 else ('S%d' % state)
ps2 = ' '.join([str(t[0]) for t in out])
print('-- ')
print('%s (%d) [%s]' % (ps0, len(out), ps2))
print()
# Return final state and tape...
return (state, out)
#
It has something of a small bug that I’ll get to later. I wrote one I like better, and I fixed the bug in that one. This one was just an excuse to use a Python generator to implement the tape.
It popped into my head that the async nature of generators meant one could sit over on the side managing the tape. The interface is simple, just a symbol to write to the current position and a direction to move the tape. The only return value we need is the current value on the tape.
Here it is:
def turing_tape (tape, Blank=0):
'''Turing Machine Tape (Python generator)'''
head = 0
while True:
_tval,_move = yield tape[head][0]
tval = int(_tval)
move = int(_move)
# Write to the tape...
tape[head][0] = tval
tape[head][1] += 1
# Move forwards...
if 0 < move:
head += 1
# Append another cell if necessary...
if len(tape) <= head:
tape.append([Blank,0])
continue
# Move backwards...
if move < 0:
head -= 1
# Insert another cell if necessary...
if head < 0:
head = 0
tape.insert(0, [Blank,0])
continue
# Don't move (move==0)...
#
It requires an initial tape, a list object. If it needs to move to the left beyond the tape, it inserts new cells at the beginning. If it runs off the end of the tape, it appends new cells to the end. The only tape limit is system memory and/or whatever Python would choke on.
Note each tape cell is a list, [n, m], where n is the cell contents, and m is a count of the times the cell has been written to. That allows some stats on tape use.
Run it very simply with:
final,tape = turing_machine(pgm1, max_steps=15) #
When run the TM prints:
1: S0 [0] {1,R} (S1)
2: S1 [0] {0,R} (S2)
3: S2 [0] {2,R} (S3)
4: S3 [0] {0,R} (S0)
5: S0 [0] {1,R} (S1)
6: S1 [0] {0,R} (S2)
7: S2 [0] {2,R} (S3)
8: S3 [0] {0,R} (S0)
9: S0 [0] {1,R} (S1)
10: S1 [0] {0,R} (S2)
11: S2 [0] {2,R} (S3)
12: S3 [0] {0,R} (S0)
13: S0 [0] {1,R} (S1)
14: S1 [0] {0,R} (S2)
15: S2 [0] {2,R} (S3)
--
S3 (15) [1 0 2 0 1 0 2 0 1 0 2 0 1 0 2]
Which is a list of the steps the TM took. Each step lists the step number, current state, current tape value, the action (what to write and which direction to move), and the next state to go to.
The program we gave it just loops through its states over and over until the watchdog kicks the program out of the pool. It constantly moves to the right, so it always sees a blank on the tape [0].
The line at the bottom is the final state, the length of the tape, and the tape itself. Here the blanks between numbers are not part of the tape. They’re inserted for clarity.
§ §
That was interesting enough, but it was mainly to implement a Python generator function for the tape. I don’t love the implementation. And there is a bug in the part that’s intended to trim off any unused ends of the tape. It will remove any cell with a use-counter of zero, not just the ones at the end.
There are myriad ways to remove the cat’s skin, though, and being class conscious… or rather that is to say, being a classy programmer, I like an implementation with class.
So, I re-wrote the Turing Machine as a pair of classes. First the tape:
class TuringTape (object):
def __init__ (self, blank=0):
self.blank = blank
self.reset()
def reset (self):
self.head = 0
self.tape = [[self.blank, 0]]
def curr (self):
return self.tape[self.head][0]
def __call__ (self, cell, move):
_cell = int(cell)
_move = int(move)
# Write to the tape...
self.tape[self.head][0] = _cell
self.tape[self.head][1] += 1
# Move forwards...
if 0 < _move:
self.head += 1
# Append another cell if necessary...
if len(self.tape) <= self.head:
self.tape.append([self.blank,0])
return
# Move backwards...
if _move < 0:
self.head -= 1
# Insert another cell if necessary...
if self.head < 0:
self.head = 0
self.tape.insert(0, [self.blank,0])
return
# Don't move (_move==0)...
def __len__ (self):
return len(self.tape)
def __str__ (self):
t = ' '.join([str(t0) for t0,t1 in self.tape if t1])
return '[%s]' % t
def _trim (self):
while (1 < len(self)) and (self.tape[-1][1] == 0):
self.tape.pop(-1)
while (1 < len(self)) and (self.tape[0][1] == 0):
self.tape.pop(0)
#
It has more features than a generator function, obviously.
And here’s the machine:
class TuringMachine (object):
def __init__ (self, program, max_steps=32, blank=0):
self.program = program
self.max_steps = max_steps
self.state = 0
self.watchdog = 1
self.tape = TuringTape(blank=blank)
def reset (self):
self.state = 0
self.watchdog = 1
self.tape.reset()
def run (self):
while 0 <= self.state:
pe = self._find_pgm_entry()
d = 'L' if pe[3]<0 else 'R'
x = 'HALT' if pe[4] < 0 else ('S%d' % pe[4])
s = '%2d: S%d [%d] {%d,%s} (%s)'
t = (self.watchdog, self.state, self.tape.curr(), pe[2],d, x)
print(s % t)
self.tape(pe[2], pe[3])
self.state = pe[4]
self.watchdog += 1
if self.max_steps < self.watchdog:
break
# Trim (we assume) unused tape ends...
self.tape._trim()
out = [(t0,t1) for t0,t1 in self.tape.tape if t1]
# Generate a nice print string...
ps0 = 'HALT' if self.state < 0 else ('S%d' % self.state)
ps2 = ' '.join([str(t[0]) for t in out])
print('-- ')
print('%s (%d) [%s]' % (ps0, len(out), ps2))
print()
# Return final state and tape...
return (self.state, out)
def __str__ (self):
return ''
def _find_pgm_entry (self):
for pe in self.program:
if (pe[0]==self.state) and (pe[1]==self.tape.curr()):
return pe
raise KeyError('No Program Entry!')
#
A TuringMachine object doesn’t auto-run. That takes the run method:
tm1 = TuringMachine(pgm1, max_steps=15) final,tape = tm1.run() #
When run it prints exactly the same thing as the first one.
§ §
Now that we have a Turing Machine that runs the first example, we can try some others. Here’s one called the three-state busy beaver:
# 3-State Busy Beaver
pgm2 = (
(0, 0, 1, +1, 1),
(0, 1, 1, -1, 2),
(1, 0, 1, -1, 0),
(1, 1, 1, +1, 1),
(2, 0, 1, -1, 1),
(2, 1, 1, 0, -1),
)
When run, it moves back and forth on the tape writing a new 1 at each edge and then turning around for the other edge. It causes the tape to grow in both directions one cell at a time. But it only runs for 13 steps — it has a halting condition. In those 13 steps, it creates a tape of six 1s.
When run, the output looks like this:
1: S0 [0] {1,R} (S1)
2: S1 [0] {1,L} (S0)
3: S0 [1] {1,L} (S2)
4: S2 [0] {1,L} (S1)
5: S1 [0] {1,L} (S0)
6: S0 [0] {1,R} (S1)
7: S1 [1] {1,R} (S1)
8: S1 [1] {1,R} (S1)
9: S1 [1] {1,R} (S1)
10: S1 [1] {1,R} (S1)
11: S1 [0] {1,L} (S0)
12: S0 [1] {1,L} (S2)
13: S2 [1] {1,R} (HALT)
--
HALT (6) [1 1 1 1 1 1]
The Wiki page for Turing Machine has a lot of detail about how this runs. Check out the Turing Machine examples Wiki page for more details and other programs you can try.
§ §
Quite some time ago, for some other blog post, I created a 3D model of an imaginary Turing Machine in POV-Ray (a powerful free ray-tracing software). Here it is:
Note the “infinite” reels for the tape. I gave it a lot of blinky lights to make it look cool, but we know a TM is really simple.
Ø
The Hard-Core Coder 
This was a fun afternoon project. I’ll have to write up some of my other fun diversions!