#!/usr/bin/env python

"""Simulates a Turing machine on some input.
   
   The turing machine is describes as a dictionary of tuples
   the keys are tuples of (state, symbol), and the tuples consists of
   1. symbol to write on tape
   2. direction to move ('L' or 'R')
   3. state to transition to

   Input to the simulator is a configuration of a machine.
   That is a tape (list of symbols), a number for which cell is currently
   being looked at by the machine (indexing begins at 0), and the name of
   the current state.

   As the simulator emulates the turing machine, it will yield the successive
   configurations.

   At any time during the simulation:
     If the simulation encounters a (symbol,state) transition key which
        is not in the dictionary, then we yield 'crash' and halt.
     If the simulated machine accepts, then we yield 'accept' and halt.
     If the simulated machine rejects, then we yield 'reject' and halt.
   There will be no attept to detect infinite loops.

   Blanks on this tape are 0's and extend infinitely in both directions.
   It is recommended that all states an symbols have TeX encoding,
   in this way we assure pretty printing.

   Output is a sequence of machine configurations printed to the screen.
"""

# the transition map for 2-state 3-symbol Busy Beaver
UTM = {
    ('$q_A$', '0') : ('1', 'L', '$q_B$'),
    ('$q_A$', '1') : ('1', 'R', '$q_C$'),

    ('$q_B$', '0') : ('1', 'R', '$q_A$'),
    ('$q_B$', '1') : ('1', 'L', '$q_B$'),

    ('$q_C$', '0') : ('1', 'R', '$q_B$'),
    ('$q_C$', '1') : ('1', 'L', 'accept')
    }

STARTCONFIG = ( list('0000000000'), 4, '$q_A$' )


def simulate_step( machine, config ):
    tape, position, state = config;

    # look up the transition

    try:
        write_symbol, move, next_state = machine[ (state, tape[position]) ]
    except KeyError:
        return 'crash'

    if next_state in ['reject', 'accept', 'crash']:
        return next_state

    if move == 'R':
        # fix the tape if we run off the right end
        if position+1 >= len(tape):
            tape += ['0']*(position+2-len(tape))

        return ( tape[:position] + [write_symbol] + tape[position+1:],
                 position+1,
                 next_state )

    elif move == 'L':
        # fix the tape if we run off the left end
        if position <= 0:
            tape = ['0'] + tape
            position += 1

        return ( tape[:position] + [write_symbol] + tape[position+1:],
                 max( position-1, 0), # prevent walking off left end of tape
                 next_state )

    else:
        return 'crash'


def config_to_str( config ):
    tape, position, state = config
    return ''.join( tape[:position] + [state] + tape[position:] )
    
def machine_to_str( machine ):
    lst = ['\\begin{tabular}{cc|ccc}']
    lst += ['\\multicolumn{2}{c|}{current}&\\multicolumn{3}{c}{ }\\\\']
    lst += ['state&symbol&print&move&new-state\\\\']
    lst += ['\\hline']
    
    for key in sorted(machine.keys()):
        s = '&'.join(map(str, key))
        p = '&'.join(map(str, machine[key]))
        lst.append( s + '&' + p + '\\\\' )

    lst.append( '\\end{tabular}' )
    return '\n'.join(lst)
            

if __name__=='__main__':
    machine = UTM
    config = STARTCONFIG

    print '\\documentclass[a4paper,10pt]{article}'
    print '\\title{3-state 2-symbol Busy Beaver}'
    print '\\begin{document}'
    print '\\tt'
    print '\\maketitle'

    print machine_to_str(machine)
    print '\\\\ '
    print '\\\\ '
    print

    count = 0
    while 1:
        count += 1
        print '%02d'%count, '\\ \\ \\ ', config_to_str( config )
        print
        config = simulate_step( machine, config )
        if config in ['reject', 'accept', 'crash']:
            break

    print config
    print
    print '\\end{document}'