#!/usr/bin/python
# Busy Beaver Turing machine
# http://en.wiki.x.io/wiki/Busy_beaver
# Create GIF animation with ImageMagick:
# convert -delay 90 beaver_step*.png -loop 0 b.gif
from PIL import Image, ImageDraw, ImageFont
cell = 40 * [0] # tape array
left, right = 19, 24 # plot limits
fs = 120
w, h = (right - left + 1) * 84, 3 * fs
fnt = ImageFont.truetype('Courier Prime.ttf', fs)
bp = len(cell) // 2 # starting position
bs = "A" # initial state
# 3-state, 2-symbol
tab3 = {
"A": ["1RB", "1RH"],
"B": ["0RC", "1RB"],
"C": ["1LC", "1LA"],
}
# 4-state, 2-symbol
tab4 = {
"A": ["1RB", "1LB"],
"B": ["1LA", "0LC"],
"C": ["1RH", "1LD"],
"D": ["1RD", "0RA"],
}
# select table to use
tab = tab3
step = -1
while True:
out = "".join([str(x) for x in cell])
out2 = out[:bp] + bs + out[bp+1:]
out = out[left:right+1]
out2 = out2[left:right+1]
print(out2)
step += 1
im = Image.new('RGBA', (w, h), (0,0,0))
d = ImageDraw.Draw(im)
d.text((0, 0), out, font = fnt, fill = (255,255,0), align = "left")
d.text((0, fs), (bp - left) * " " + bs, font = fnt, fill = (255,0,0), align = "left")
d.text((0, 2 * fs), "STEP %u" % step, font = fnt, fill = (0,255,0), align = "left")
im.save("beaver_step%04u.png" % step)
if bs == "H":
for n in range(step + 1, step + 3):
im.save("beaver_step%04u.png" % n)
break
cmd = tab[bs][cell[bp]]
cell[bp] = int(cmd[0])
if cmd[1] == 'R':
bp += 1
if cmd[1] == 'L':
bp -= 1
bs = cmd[2]