Post’s Machine Emulator

January 17th, 2009 · 2 Comments · Computer Science, Mathematics, python

I was bored as usual and since Combat Arms has begun to slip in my list of pastimes, I decided to write a Post’s Machine Emulator as described in the booklet by V. A. Uspensky titled “Post’s Machine” ( Amazon Link

This machine has a tape (infinitely long) and the reel has cells which can be marked or unmarked. I decided to represent a marked cell with a “1″ and an unmarked cell as “0″.

The head of this machine can move both ways and can mark and at the same time remove the mark from the other side.

The machine can be instructed using the syntax:

number, action, jump

The position of the head is indicated by a structure \”[]\” around the cell. Example:

Initial Stage
.....[0], 0, 0, 0, 0, .....

I used the “…..” to indicate that the remnant cells are all unmarked.

So here are the Head and Tape classes:

class Cell:
”‘Class describing the cell of a tape’”

def __init__(self, mark=0):
”‘Each cell is unmarked by default’”
self.mark = mark

def setMark(self):
self.mark = 1

def remMark(self):
self.mark = 0

class Tape:
”‘Class describing the infinite reel in the machine’”

def __init__(self):
”‘Each tape has an infinite number of cells both ways’”
self.reel = []
for i in xrange(5): #we display only the required elements at a time
cell = Cell()
self.reel.append(cell)

def __str__(self):
printstr = "….."
for cell in self.reel:
printstr += str(cell.mark)+","
printstr += "….."
return printstr

class Head:
”‘Class describing the head’”

def __init__(self, tape, position=0):
self.position = position
self.tape = tape

def moveLeft(self):
if self.position != 0:
self.position -= 1

else:
extension = []
extension.append(Cell())
self.tape = extension + tape.reel

def etchMark(self):
self.tape.reel[self.position].setMark()

def remMark(self):
self.tape.reel[self.position].remMark()

def moveRight(self):
if self.position == len(self.tape.reel) – 1:
self.tape.reel.append(Cell())
self.position += 1

def getPosition(self):
return self.position

Then comes the Machine class which takes a tape as an argument. So that you can insert your own tape or use the default tape:

class Machine:
”‘Class describing the Post Machine’”

def __init__(self, tape):
self.tape = tape
self.head = Head(tape)
self.commands = {}

def parseInstruction(self, number, action, jump):
”‘Instruction is of form "[number, action, jump]"’”
self.commands[number] = [action, jump]

def beginExecution(self):
instruction = 0
action = self.commands[instruction][0]

while action != "exit":
if action == "<":
self.head.moveLeft()
elif action == ">":
self.head.moveRight()
elif action == "mark":
self.head.etchMark()
elif action == "unmark":
self.head.remMark()

print self
instruction = self.commands[instruction][1]
action = self.commands[instruction][0]

return

def __str__(self):
”‘This returns tape with the head displayed’”
a = str(self.tape)
posn = self.head.getPosition()
temp = "….."
for i in xrange(len(self.tape.reel)):
if i == posn:
temp += "["+str(self.tape.reel[i].mark)+"], "
else:
temp += str(self.tape.reel[i].mark) + ", "
temp += "….."
return temp

Next comes a function that reads an input file for instructions:

def run(input_file):
infile = open(input_file, ‘r’)
b = infile.readlines()
for instruction in b:
try:
splits = instruction.split(",")
number = int(splits[0].strip())
action = splits[1].strip()
if action == "exit":
a.parseInstruction(number, action, 0)
else:
jump = int(splits[2].strip())
a.parseInstruction(number, action, jump)
except KeyError:
return
infile.close()
a.beginExecution()

A bunch of instructions which need to be written to some file:

0, >, 2
1, <, 0
2, >, 3
3, >, 4
4, >, 5
5, mark, 6
6, >, 7
7, exit

The output:

pal-178-222:~ shriphani$ python post.py
Initial Stage
.....[0], 0, 0, 0, 0, .....
File: input_file
.....0, [0], 0, 0, 0, .....
.....0, 0, [0], 0, 0, .....
.....0, 0, 0, [0], 0, .....
.....0, 0, 0, 0, [0], .....
.....0, 0, 0, 0, [1], .....
.....0, 0, 0, 0, 1, [0], .....
pal-178-222:~ shriphani$ python post.py

The full script can be obtained at http://shriphani.com/scripts/post.py

Well, later.

Tags: