# Notes from Wednesday, October 25

# A Universal Turing Machine (UTM) simulator in Python

import string

# loadTM takes the name of a file containing a Turing machine
# description and returns a list of rules representing that machine

def loadTM(filename):
    TMfile = open(filename)
    rules = []
    for line in TMfile:
        # ignore blank lines and comments
        if line == "\n" or line[0] == "#":
            pass
        else:
            rule = string.split(line)
            rules.append(rule)
    TMfile.close()
    return rules


# determineAction takes a state, a symbol, and a list of Turing
# machine rules TM, and returns a tuple (newState, newSymbol, move)
# indicating what action to take in response to the given state and
# symbol

def determineAction(state, symbol, TM):
    for rule in TM:
        (currentState, currentSymbol, newState, newSymbol, move) = rule
        # see if this is the rule we're looking for
        if currentState == state and currentSymbol == symbol:
            return (newState, newSymbol, move)
    # no appropriate rule found
    return None


# utm simulates the behavior of a Turing machine TM (represented as a
# list of rules) on a given input string

def utm(TM, tapeContents):
    # TM is a list of Turing machine rules, where each rule is a list of
    # the form [<oldState>, <oldSymbol>, <newState>, <newSymbol>, <move>].
    # tapeContents is a string that specifies the initial contents of the
    # input tape.

    # initialize the tape and machine state
    tape = []
    for symbol in tapeContents:
        tape.append(symbol)
    headPosition = 0
    state = "A"

    # run the machine
    while True:

        # print out the tape in a nice form
        printTape(tape, headPosition)

        # determine the next action to perform, if any
        symbol = tape[headPosition]
        action = determineAction(state, symbol, TM)
        if action is None:
            break
        else:
            (newState, newSymbol, move) = action

        # write the new symbol on the tape
        tape[headPosition] = newSymbol
        # change to the new state
        state = newState
        # update the tape head position
        if move == "right":
            headPosition = headPosition + 1
        elif move == "left":
            headPosition = headPosition - 1
        else:
            print "error: unknown move encountered"
            break

    print "halted"


# printTape prints out the tape, with the position of the read/write
# head indicated by []'s

def printTape(tape, headPosition):
    s = ""
    for i in range(len(tape)):
        if i == headPosition:
            s = s + "[" + tape[i] + "]"
        else:
            s = s + " " + tape[i] + " "
    print s


#--------------------------------------------------------------------
# Example:
# 
# >>> inverter = loadTM("inverter.tm")
# 
# >>> inverter
# [['A', '0', 'A', '1', 'right'],
#  ['A', '1', 'A', '0', 'right'],
#  ['A', '_', 'B', '_', 'right']]
# 
# >>> utm(inverter, "0100____")
# [0] 1  0  0  _  _  _  _ 
#  1 [1] 0  0  _  _  _  _ 
#  1  0 [0] 0  _  _  _  _ 
#  1  0  1 [0] _  _  _  _ 
#  1  0  1  1 [_] _  _  _ 
#  1  0  1  1  _ [_] _  _ 
# halted
# >>>