# TM_Sim_2.py
# Turing Machine in Python - M. Earnshaw 2010

state = 0
haltAfter = 100
step = 0
pos = 0

# Instructions:
# Actions take the form: (currentState, currentSymbol):(nextSymbol, moveDirection, nextState)
# Use 'halt' to halt, 'b' for blank, 'l' for move left, 'r' for move right, 'n' for no move.

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 
# # # Unary Add Program # # #
# Adds two unary numbers seperated by a 'b'. 

"""tape = ['b',1,1,1,'b',1,1,1,1]
transitionFunction = 	{\
 			(0,'b'):('b','r',0), \
 			(0,1):(1,'r',1), \
 			(1,'b'):(1,'r',2), \
 			(1,1):(1,'r',1), \
 			(2,'b'):('b','l',3), \
 			(2,1):(1,'r',2), \
 			(3,'b'):('b','l',3), \
 			(3,1):('b','l',4), \
            (4,'b'):('b','r','halt'), \
 			(4,1):(1,'l',4) \
 			}"""

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 
# # # 3-state Busy Beaver # # #

"""tape = []
transitionFunction =	{\
			(0,0):(1,'r',1), \
			(0,1):(1,'n','halt'), \
			(0,'b'):(1,'r',1), \
			(1,0):(0,'r',2), \
			(1,1):(1,'r', 1), \
			(1,'b'):(0,'r',2), \
			(2,0):(1,'l',2), \
			(2,1):(1,'l', 0), \
			(2,'b'):(1,'l',2), \
			}"""

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 
# # # Turing's Original Program # # # 
# Fills the tape with 1010101...

tape = []
transitionFunction = 	{
			(0,'b'):(1,'r',1),
			(1,'b'):(0,'r',0)
			}

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 

# # # Binary increment # # # 
# Increments number on tape by 1.

"""tape = [1,1,1,1,0,1,0,1,0]

transitionFunction =	{			
			# Scan to end of tape
			(0,1):(1,'r',0),
			(0,0):(0,'r',0),
			(0,'b'):('b','l',1),

            (1,0):(1,'n','halt'),
            (1,1):(0,'r',2),

			(2,'b'):(0,'n','halt')
			}"""

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # #


def halt(msg): raw_input("\nHalted. " + msg)

def readSymbol(pos):
    try:
    	symbol = tape[pos]
    	return symbol
    except IndexError:
    	return 'b' # treats undefined positions on tape as blank.

def outputTape(pos):
    for i in tape[:pos]:
        if i!='b': print i,",",

    print "[",tape[pos],"]",
            
    for i in tape[pos+1:len(tape)]:
        if i!='b': print i,",",
    
    print tape[len(tape)-1]
    

def addSymbol(state, symbol, pos):
    try:
        tape[pos] = transitionFunction[state,symbol][0]
    except:
        tape.append(transitionFunction[state,symbol][0])

def doTransition(state, symbol, pos):
    global step
    if step < haltAfter:

        if state == 'halt': halt("Completed successfully.")
        
        step+=1
    
        if transitionFunction.has_key((state, symbol)):

            addSymbol(state, symbol, pos)
            
            outputTape(pos)
        
            if transitionFunction[state,symbol][1] == 'r':
                pos += 1
            elif transitionFunction[state,symbol][1] == 'l':
                pos -= 1
    
            newState = transitionFunction[state,symbol][2]
    
            newSymbol = readSymbol(pos)
        
            doTransition(newState, newSymbol, pos)
            
        else:
            halt("No action found for symbol: " + str(symbol) + " in state: " + str(state) )
    else:
        halt("Reached step limit.")

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

print "\nTuring Machine Simulator - M. Earnshaw"

# start the machine
doTransition(state,readSymbol(pos),pos)