Skip to content

Instantly share code, notes, and snippets.

@mbasaglia
Last active August 11, 2017 14:24
Show Gist options
  • Save mbasaglia/5fbd551b06171d5cea3378b21b8a9696 to your computer and use it in GitHub Desktop.
Save mbasaglia/5fbd551b06171d5cea3378b21b8a9696 to your computer and use it in GitHub Desktop.
Turing machine implementation in Python, with a couple examples
#!/usr/bin/env python
class Tape(object):
def __init__(self, data="", blank=None):
self.tape = dict(enumerate(data))
self.pos = 0
self.blank = blank
def move_right(self):
self.pos += 1
def move_left(self):
self.pos -= 1
def read(self):
return self.read_at(self.pos)
def read_at(self, pos):
return self.tape.get(pos, self.blank)
def write(self, value):
self.tape[self.pos] = value
def render(self):
range_min = min(min(self.tape.keys()), self.pos)
range_max = max(max(self.tape.keys()), self.pos)
for i in xrange(range_min, range_max+1):
val = self.read_at(i)
txt = str(val) if val is not None else ''
if i == 0:
txt += " (start)"
if i == self.pos:
txt += " <--"
print txt
class NumericTape(Tape):
def __init__(self, data="", blank=None):
return super(NumericTape, self).__init__(
map(lambda x: int(x) if x != " " else blank, data),
blank
)
class TextTape(Tape):
def __init__(self, data=""):
return super(TextTape, self).__init__(data, " ")
class Instruction(object):
LEFT = Tape.move_left
RIGHT = Tape.move_right
NOOP = staticmethod(lambda x: None)
def __init__(self, write, move, next):
self.write = write
self.move = move
self.next = next
class Halt(Instruction):
def __init__(self):
pass
class Machine(object):
def __init__(self, states, initial_state):
self.states = states
self.initial_state = initial_state
class MachineRunner(object):
def __init__(self, machine, tape, debug=False):
self.machine = machine
self.tape = tape
self.instruction = self.get_instruction(self.machine.initial_state)
self.debug = debug
def get_instruction(self, state_name):
if state_name is Halt:
return Halt()
return self.machine.states[(state_name, self.tape.read())]
def execute_one(self):
if self.halted():
return
if self.debug:
print "---"
self.tape.render()
print "---"
print self.instruction.next
self.tape.write(self.instruction.write)
self.instruction.move(self.tape)
self.instruction = self.get_instruction(self.instruction.next)
def execute(self):
while not self.halted():
self.execute_one()
return self.tape
def halted(self):
return isinstance(self.instruction, Halt)
# Tri-state busy beaver
"""
MachineRunner(
Machine(
{
("a", 0): Instruction(1, Instruction.RIGHT, 'b'),
("a", 1): Instruction(1, Instruction.RIGHT, Halt),
("b", 0): Instruction(0, Instruction.RIGHT, 'c'),
("b", 1): Instruction(1, Instruction.RIGHT, 'b'),
("c", 0): Instruction(1, Instruction.LEFT, 'c'),
("c", 1): Instruction(1, Instruction.LEFT, 'a'),
},
"a"
),
Tape(blank=0)
).execute().render()
"""
# Add 1 in binary
"""
MachineRunner(
Machine(
{
("a", None): Instruction(None, Instruction.LEFT, 'b'),
("a", 0): Instruction(0, Instruction.RIGHT, 'a'),
("a", 1): Instruction(1, Instruction.RIGHT, 'a'),
("b", None): Instruction(1, Instruction.RIGHT, Halt),
("b", 0): Instruction(1, Instruction.RIGHT, Halt),
("b", 1): Instruction(0, Instruction.LEFT, 'b'),
},
"a"
),
Tape(map(int, "100011"))
).execute().render()
"""
# Add 1 in decimal
"""
MachineRunner(
Machine(
{
("a", None): Instruction(None, Instruction.LEFT, 'b'),
("a", 0): Instruction(0, Instruction.RIGHT, 'a'),
("a", 1): Instruction(1, Instruction.RIGHT, 'a'),
("a", 2): Instruction(2, Instruction.RIGHT, 'a'),
("a", 3): Instruction(3, Instruction.RIGHT, 'a'),
("a", 4): Instruction(4, Instruction.RIGHT, 'a'),
("a", 5): Instruction(5, Instruction.RIGHT, 'a'),
("a", 6): Instruction(6, Instruction.RIGHT, 'a'),
("a", 7): Instruction(7, Instruction.RIGHT, 'a'),
("a", 8): Instruction(8, Instruction.RIGHT, 'a'),
("a", 9): Instruction(9, Instruction.RIGHT, 'a'),
("b", None): Instruction(1, Instruction.LEFT, Halt),
("b", 0): Instruction(1, Instruction.LEFT, Halt),
("b", 1): Instruction(2, Instruction.LEFT, Halt),
("b", 2): Instruction(3, Instruction.LEFT, Halt),
("b", 3): Instruction(4, Instruction.LEFT, Halt),
("b", 4): Instruction(5, Instruction.LEFT, Halt),
("b", 5): Instruction(6, Instruction.LEFT, Halt),
("b", 6): Instruction(7, Instruction.LEFT, Halt),
("b", 7): Instruction(8, Instruction.LEFT, Halt),
("b", 8): Instruction(9, Instruction.LEFT, Halt),
("b", 9): Instruction(0, Instruction.LEFT, 'b'),
},
"a"
),
Tape(map(int, "10012399"))
).execute().render()
"""
# Reverse Binary
"""
MachineRunner(
Machine(
{
# Shift by 1 place to the righ (and delete last digit)
("Shift-s", None): Instruction(None, Instruction.LEFT, Halt),
("Shift-s", 0): Instruction(None, Instruction.RIGHT, 'Shift-0'),
("Shift-s", 1): Instruction(None, Instruction.RIGHT, 'Shift-1'),
("Shift-0", None): Instruction(None, Instruction.LEFT, 'Place-0'),
("Shift-0", 0): Instruction(0, Instruction.RIGHT, 'Shift-0'),
("Shift-0", 1): Instruction(0, Instruction.RIGHT, 'Shift-1'),
("Shift-1", None): Instruction(None, Instruction.LEFT, 'Place-1'),
("Shift-1", 0): Instruction(1, Instruction.RIGHT, 'Shift-0'),
("Shift-1", 1): Instruction(1, Instruction.RIGHT, 'Shift-1'),
# Place a digit before the first blank
("Place-0", None): Instruction(None, Instruction.LEFT, 'Place-0-done'),
("Place-0", 0): Instruction(0, Instruction.LEFT, 'Place-0'),
("Place-0", 1): Instruction(1, Instruction.LEFT, 'Place-0'),
("Place-0-done", None): Instruction(0, Instruction.RIGHT, 'Rewind'),
("Place-0-done", 0): Instruction(0, Instruction.LEFT, 'Place-0-done'),
("Place-0-done", 1): Instruction(1, Instruction.LEFT, 'Place-0-done'),
("Place-1", None): Instruction(None, Instruction.LEFT, 'Place-1-done'),
("Place-1", 0): Instruction(0, Instruction.LEFT, 'Place-1'),
("Place-1", 1): Instruction(1, Instruction.LEFT, 'Place-1'),
("Place-1-done", None): Instruction(1, Instruction.RIGHT, 'Rewind'),
("Place-1-done", 0): Instruction(0, Instruction.LEFT, 'Place-1-done'),
("Place-1-done", 1): Instruction(1, Instruction.LEFT, 'Place-1-done'),
# Find start (the position after the first blank)
("Rewind", None): Instruction(None, Instruction.RIGHT, "Shift-s"),
("Rewind", 0): Instruction(0, Instruction.RIGHT, 'Rewind'),
("Rewind", 1): Instruction(1, Instruction.RIGHT, 'Rewind'),
},
"Shift-s"
),
Tape(map(int, "10001101"))
).execute().render()
"""
# Strlen, writes the number of consecutive non-blank places in the tapes (in binary)
"""
MachineRunner(
Machine(
{
# Initialize the counter (1 blank to the left of the string)
("Start", None): Instruction(0, Instruction.RIGHT, Halt), # Empty tape, just write 0 and halt
("Start", 0): Instruction(None, Instruction.LEFT, "Start-write"), # If not empty, write a blank
("Start", 1): Instruction(None, Instruction.LEFT, "Start-write"), # and initialize the counter with 1
("Start-write", None): Instruction(1, Instruction.RIGHT, "GotoEnd"),# Write the 1 (the tape isn't empty)
("Start-write", 0): Instruction(1, Instruction.RIGHT, Halt), # The tape has garbage data
("Start-write", 1): Instruction(1, Instruction.RIGHT, Halt), # The tape has garbage data
# Go to the end of the string
("GotoEnd", None): Instruction(None, Instruction.RIGHT, "FindEnd"), # Skip the counter digits
("GotoEnd", 0): Instruction(0, Instruction.RIGHT, "GotoEnd"),
("GotoEnd", 1): Instruction(1, Instruction.RIGHT, "GotoEnd"),
("FindEnd", None): Instruction(None, Instruction.LEFT, "Found"), # Skip until a blank
("FindEnd", 0): Instruction(0, Instruction.RIGHT, "FindEnd"),
("FindEnd", 1): Instruction(1, Instruction.RIGHT, "FindEnd"),
# Record the fact we found a character
("Found", None): Instruction(None, Instruction.LEFT, Halt), # Nothing left
("Found", 0): Instruction(None, Instruction.LEFT, "FindCounter"), # Remove the last digit
("Found", 1): Instruction(None, Instruction.LEFT, "FindCounter"),
# Go back to the counter
("FindCounter", None): Instruction(None, Instruction.LEFT, "Increment"),
("FindCounter", 0): Instruction(0, Instruction.LEFT, "FindCounter"),
("FindCounter", 1): Instruction(1, Instruction.LEFT, "FindCounter"),
# Add 1 to the counter
("Increment", None): Instruction(1, Instruction.RIGHT, "GotoEnd"),
("Increment", 0): Instruction(1, Instruction.RIGHT, "GotoEnd"),
("Increment", 1): Instruction(0, Instruction.LEFT, "Increment"),
},
"Start"
),
Tape(map(int, "100011101")),
).execute().render()
"""
# Decrement binary integer
"""
MachineRunner(
Machine(
{
("find-right", None): Instruction(None, Instruction.LEFT, 'decrement'),
("find-right", 0): Instruction(0, Instruction.RIGHT, 'find-right'),
("find-right", 1): Instruction(1, Instruction.RIGHT, 'find-right'),
("decrement", None): Instruction(1, Instruction.RIGHT, Halt),
("decrement", 0): Instruction(1, Instruction.LEFT, 'decrement'),
("decrement", 1): Instruction(0, Instruction.RIGHT, Halt),
},
"find-right"
),
Tape(map(int, "101100")),
).execute().render()
"""
# Binary Sum
"""
MachineRunner(
Machine(
{
# Go to the end (needs to skip a blank)
("find-end", None): Instruction(None, Instruction.RIGHT, "find-end-n2"),
("find-end", 0): Instruction(0, Instruction.RIGHT, "find-end"),
("find-end", 1): Instruction(1, Instruction.RIGHT, "find-end"),
("find-end-n2", None): Instruction(None, Instruction.LEFT, "decrement"),
("find-end-n2", 0): Instruction(0, Instruction.RIGHT, "find-end-n2"),
("find-end-n2", 1): Instruction(1, Instruction.RIGHT, "find-end-n2"),
# Decrement n2
("decrement", None): Instruction(None, Instruction.RIGHT, "clear"),
("decrement", 0): Instruction(1, Instruction.LEFT, "decrement"),
("decrement", 1): Instruction(0, Instruction.NOOP, "find-n1"),
# Find the end of n1
("find-n1", None): Instruction(None, Instruction.LEFT, "increment"),
("find-n1", 0): Instruction(0, Instruction.LEFT, "find-n1"),
("find-n1", 1): Instruction(1, Instruction.LEFT, "find-n1"),
# Increment n1
("increment", None): Instruction(1, Instruction.NOOP, "find-end"),
("increment", 0): Instruction(1, Instruction.NOOP, "find-end"),
("increment", 1): Instruction(0, Instruction.LEFT, "increment"),
# Clear n2
("clear", None): Instruction(None, Instruction.LEFT, Halt),
("clear", 0): Instruction(None, Instruction.RIGHT, "clear"),
("clear", 1): Instruction(None, Instruction.RIGHT, "clear"),
},
"find-end"
),
NumericTape("10011 110"),
).execute().render()
"""
from io import BytesIO
class TMDescriptionParser(object):
class ParserError(Exception):
pass
movement = {
"<": Instruction.LEFT,
">": Instruction.RIGHT,
"-": Instruction.NOOP,
}
@classmethod
def machine_from_string(cls, string):
return cls(BytesIO(string)).parse_one()
def __init__(self, file_obj):
self.input = file_obj
def parse_many(self):
machines = []
while True:
machines.append(self._parse_machine())
ch = self._getchar(None)
if not ch:
break
elif ch != ";":
raise self.ParserError("Extra characters after machine definition")
return machines
def parse_one(self):
machine = self._parse_machine()
if self._getchar(None):
raise self.ParserError("Extra characters after machine definition")
return machine
def _parse_machine(self):
alphabet = self._parse_alphabet()
return self._parse_states(alphabet)
def _getchar(self, expected):
char = self.input.read(1)
if not char and expected:
raise self.ParserError("End of stream, expected %s" % expected)
return char
def _read_until(self, boundary, required=True):
result = ""
while True:
char = self._getchar(boundary if required else None)
if char in boundary or (not required and not char):
return result, char
result += char
def _parse_alphabet(self):
result = []
while True:
alphabet, delim = self._read_until(":\\")
result += list(alphabet)
if delim == ":":
break
else:
result += [self._getchar("\\ or :")]
if len(result) != len(set(result)):
raise self.ParserError("Duplicate characters in the alphabet definition")
return result
def _parse_state_name(self):
name, delim = self._read_until(":", False)
if "," in name:
raise self.ParserError("Invald state name: %s" % name)
return name
def _parse_states(self, alphabet):
states = {}
first_state = None
while True:
state_name = self._parse_state_name()
if not state_name or state_name == ';':
break
if not first_state:
first_state = state_name
for input_char in alphabet:
output_char = self._getchar("a state transition output character")
movement = self.movement.get(
self._getchar("a movement operation"),
None
)
if not movement:
raise self.ParserError("Invalid movement operation")
dest_state, delim = self._read_until(",")
if not dest_state:
dest_state = Halt
states[(state_name, input_char)] = Instruction(output_char, movement, dest_state)
if not states:
raise self.ParserError("Empty machine")
return Machine(states, first_state)
# Binary added with the compact turing machine definition mini-language
"""
adder = " 01:a: <b,0>a,1>a,b:1>,1>,0<b,;"
print MachineRunner(
TMDescriptionParser.machine_from_string(adder),
TextTape("10011")
).execute().render()
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment