#!/usr/bin/env python

import sys

"""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 the tape are designated with the TeX symbol '$\\Box$'
   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 my UTM
UTM = {
    # the start symbol
    ('$\\boldsymbol{S}$') : ('R'),
    ('$\\boldsymbol{S}$', '\\=0') : ('0', 'R', '$\\boldsymbol{S}$'),
    ('$\\boldsymbol{S}$', '\\=1') : ('1', 'R', '$\\boldsymbol{S}$'),
    ('$\\boldsymbol{S}$', 'T') : ('T', 'R', '$\\boldsymbol{T}$'),

    # hit the tape state
    ('$\\boldsymbol{T}$', '0') : ('0', 'R', '$\\boldsymbol{T}$'),
    ('$\\boldsymbol{T}$', '1') : ('1', 'R', '$\\boldsymbol{T}$'),
    ('$\\boldsymbol{T}$', 's') : ('s', 'R', '$\\boldsymbol{T}$'),
    ('$\\boldsymbol{T}$', '\\=s') : ('\\=s', 'L', '$\\boldsymbol{S_0}$'),
    ('$\\boldsymbol{T}$', '$\\Box$') : ('\\=s', 'L', '$\\boldsymbol{B_0}$'),

    # the copy blank subroutine
    ('$\\boldsymbol{B_0}$') : ('L'),
    ('$\\boldsymbol{B_0}$', 'B') : ('B', 'R', '$\\boldsymbol{B_1}$'),

    ('$\\boldsymbol{B_1}$') : ('R'),
    ('$\\boldsymbol{B_1}$', '0') : ('\\=0', 'R', '$\\boldsymbol{B_3}$'),
    ('$\\boldsymbol{B_1}$', '1') : ('\\=1', 'R', '$\\boldsymbol{B_4}$'),
    ('$\\boldsymbol{B_1}$', 'Q') : ('Q', 'L', '$\\boldsymbol{B_2}$'),
    ('$\\boldsymbol{B_1}$', '\\=Q') : ('\\=Q', 'L', '$\\boldsymbol{B_2}$'),

    ('$\\boldsymbol{B_2}$', '\\=0') : ('0', 'L', '$\\boldsymbol{B_2}$'),
    ('$\\boldsymbol{B_2}$', '\\=1') : ('1', 'L', '$\\boldsymbol{B_2}$'),
    ('$\\boldsymbol{B_2}$', 'B') : ('B', 'R', '$\\boldsymbol{S}$'),
    
    ('$\\boldsymbol{B_3}$') : ('R'),
    ('$\\boldsymbol{B_3}$', '$\\Box$') : ('0', 'L', '$\\boldsymbol{B_5}$'),

    ('$\\boldsymbol{B_4}$') : ('R'),
    ('$\\boldsymbol{B_4}$', '$\\Box$') : ('1', 'L', '$\\boldsymbol{B_5}$'),

    ('$\\boldsymbol{B_5}$') : ('L'),
    ('$\\boldsymbol{B_5}$', '\\=0') : ('\\=0', 'L', '$\\boldsymbol{B_1}$'),
    ('$\\boldsymbol{B_5}$', '\\=1') : ('\\=1', 'L', '$\\boldsymbol{B_1}$'),

    # the symbol lookup subroutine
    ('$\\boldsymbol{S_0}$') : ('L'),
    ('$\\boldsymbol{S_0}$', '\\=Q') : ('\\=Q', 'R', '$\\boldsymbol{S_1}$'),

    ('$\\boldsymbol{S_1}$') : ('R'),
    ('$\\boldsymbol{S_1}$', 'S') : ('\\=S', 'R', '$\\boldsymbol{S_2}$'),

    ('$\\boldsymbol{S_2}$', '0') : ('\\=0', 'R', '$\\boldsymbol{S_3}$'),
    ('$\\boldsymbol{S_2}$', '1') : ('\\=1', 'R', '$\\boldsymbol{S_4}$'),
    ('$\\boldsymbol{S_2}$', 'L') : ('L', 'R', '$\\boldsymbol{C_0}$'),
    ('$\\boldsymbol{S_2}$', 'R') : ('R', 'R', '$\\boldsymbol{C_0}$'),

    ('$\\boldsymbol{S_3}$') : ('R'),
    ('$\\boldsymbol{S_3}$', '\\=s') : ('\\=s', 'R', '$\\boldsymbol{S_5}$'),

    ('$\\boldsymbol{S_4}$') : ('R'),
    ('$\\boldsymbol{S_4}$', '\\=s') : ('\\=s', 'R', '$\\boldsymbol{S_6}$'),

    ('$\\boldsymbol{S_5}$', '\\=0') : ('\\=0', 'R', '$\\boldsymbol{S_5}$'),
    ('$\\boldsymbol{S_5}$', '\\=1') : ('\\=1', 'R', '$\\boldsymbol{S_5}$'),
    ('$\\boldsymbol{S_5}$', '0') : ('\\=0', 'L', '$\\boldsymbol{S_7}$'),
    ('$\\boldsymbol{S_5}$', '1') : ('1', 'L', '$\\boldsymbol{S_9}$'),

    ('$\\boldsymbol{S_6}$', '\\=0') : ('\\=0', 'R', '$\\boldsymbol{S_6}$'),
    ('$\\boldsymbol{S_6}$', '\\=1') : ('\\=1', 'R', '$\\boldsymbol{S_6}$'),
    ('$\\boldsymbol{S_6}$', '1') : ('\\=1', 'L', '$\\boldsymbol{S_7}$'),
    ('$\\boldsymbol{S_6}$', '0') : ('0', 'L', '$\\boldsymbol{S_9}$'),

    ('$\\boldsymbol{S_7}$', '\\=0') : ('\\=0', 'L', '$\\boldsymbol{S_7}$'),
    ('$\\boldsymbol{S_7}$', '\\=1') : ('\\=1', 'L', '$\\boldsymbol{S_7}$'),
    ('$\\boldsymbol{S_7}$', '\\=s') : ('\\=s', 'L', '$\\boldsymbol{S_8}$'),

    ('$\\boldsymbol{S_8}$') : ('L'),
    ('$\\boldsymbol{S_8}$', '\\=0') : ('\\=0', 'R', '$\\boldsymbol{S_2}$'),
    ('$\\boldsymbol{S_8}$', '\\=1') : ('\\=1', 'R', '$\\boldsymbol{S_2}$'),

    ('$\\boldsymbol{S_9}$') : ('L'),
    ('$\\boldsymbol{S_9}$', '\\=0') : ('0', 'L', '$\\boldsymbol{S_9}$'),
    ('$\\boldsymbol{S_9}$', '\\=1') : ('1', 'L', '$\\boldsymbol{S_9}$'),
    ('$\\boldsymbol{S_9}$', '\\=S') : ('S', 'R', '$\\boldsymbol{S_1}$'),

    # the copy symbol subroutine
    ('$\\boldsymbol{C_0}$', 's') : ('\\=s', 'R', '$\\boldsymbol{C_1}$'),

    ('$\\boldsymbol{C_1}$', '0') : ('\\=0', 'R', '$\\boldsymbol{C_2}$'),
    ('$\\boldsymbol{C_1}$', '1') : ('\\=1', 'R', '$\\boldsymbol{C_3}$'),

    ('$\\boldsymbol{C_2}$') : ('R'),
    ('$\\boldsymbol{C_2}$', '\\=s') : ('\\=s', 'R', '$\\boldsymbol{C_4}$'),

    ('$\\boldsymbol{C_3}$') : ('R'),
    ('$\\boldsymbol{C_3}$', '\\=s') : ('\\=s', 'R', '$\\boldsymbol{C_5}$'),

    ('$\\boldsymbol{C_4}$', '0') : ('0', 'R', '$\\boldsymbol{C_4}$'),
    ('$\\boldsymbol{C_4}$', '1') : ('1', 'R', '$\\boldsymbol{C_4}$'),
    ('$\\boldsymbol{C_4}$', '\\=0') : ('0', 'R', '$\\boldsymbol{C_6}$'),
    ('$\\boldsymbol{C_4}$', '\\=1') : ('0', 'R', '$\\boldsymbol{C_6}$'),

    ('$\\boldsymbol{C_5}$', '0') : ('0', 'R', '$\\boldsymbol{C_5}$'),
    ('$\\boldsymbol{C_5}$', '1') : ('1', 'R', '$\\boldsymbol{C_5}$'),
    ('$\\boldsymbol{C_5}$', '\\=0') : ('1', 'R', '$\\boldsymbol{C_6}$'),
    ('$\\boldsymbol{C_5}$', '\\=1') : ('1', 'R', '$\\boldsymbol{C_6}$'),

    ('$\\boldsymbol{C_6}$') : ('L'),
    ('$\\boldsymbol{C_6}$', '\\=s') : ('\\=s', 'L', '$\\boldsymbol{C_7}$'),
    ('$\\boldsymbol{C_6}$', 's') : ('s', 'L', '$\\boldsymbol{C_8}$'),
    ('$\\boldsymbol{C_6}$', '$\\Box$') : ('$\\Box$', 'L', '$\\boldsymbol{C_8}$'),

    ('$\\boldsymbol{C_7}$') : ('L'),
    ('$\\boldsymbol{C_7}$', '\\=0') : ('\\=0', 'R', '$\\boldsymbol{C_1}$'),
    ('$\\boldsymbol{C_7}$', '\\=1') : ('\\=1', 'R', '$\\boldsymbol{C_1}$'),

    ('$\\boldsymbol{C_8}$') : ('L'),
    ('$\\boldsymbol{C_8}$', '\\=s') : ('\\=s', 'L', '$\\boldsymbol{M_0}$'),

    # the move head subroutine
    ('$\\boldsymbol{M_0}$') : ('L'),
    ('$\\boldsymbol{M_0}$', '\\=0') : ('0', 'L', '$\\boldsymbol{M_0}$'),
    ('$\\boldsymbol{M_0}$', '\\=1') : ('1', 'L', '$\\boldsymbol{M_0}$'),
    ('$\\boldsymbol{M_0}$', '\\=s') : ('s', 'L', '$\\boldsymbol{M_1}$'),

    ('$\\boldsymbol{M_1}$', 'L') : ('L', 'R', '$\\boldsymbol{M_2}$'),
    ('$\\boldsymbol{M_1}$', 'R') : ('R', 'R', '$\\boldsymbol{M_3}$'),

    ('$\\boldsymbol{M_2}$') : ('R'),
    ('$\\boldsymbol{M_2}$', '\\=s') : ('s', 'L', '$\\boldsymbol{M_4}$'),

    ('$\\boldsymbol{M_3}$') : ('R'),
    ('$\\boldsymbol{M_3}$', '\\=s') : ('s', 'R', '$\\boldsymbol{M_5}$'),

    ('$\\boldsymbol{M_4}$') : ('L'),
    ('$\\boldsymbol{M_4}$', 's') : ('\\=s', 'L', '$\\boldsymbol{R_0}$'),
    ('$\\boldsymbol{M_4}$', 'T') : ('T', 'R', '$\\boldsymbol{M_6}$'),

    ('$\\boldsymbol{M_5}$') : ('R'),
    ('$\\boldsymbol{M_5}$', 's') : ('\\=s', 'L', '$\\boldsymbol{R_0}$'),
    ('$\\boldsymbol{M_5}$', '$\\Box$') : ('$\\Box$', 'L', '$\\boldsymbol{R_0}$'),

    ('$\\boldsymbol{M_6}$', 's') : ('\\=s', 'L', '$\\boldsymbol{R_0}$'),

    # copy state to register
    ('$\\boldsymbol{R_0}$') : ('L'),
    ('$\\boldsymbol{R_0}$', '\\=0') : ('0', 'L', '$\\boldsymbol{R_0}$'),
    ('$\\boldsymbol{R_0}$', '\\=1') : ('1', 'L', '$\\boldsymbol{R_0}$'),
    ('$\\boldsymbol{R_0}$', '\\=S') : ('\\=S', 'R', '$\\boldsymbol{R_1}$'),

    ('$\\boldsymbol{R_1}$') : ('R'),
    ('$\\boldsymbol{R_1}$', 'q') : ('\\=q', 'R', '$\\boldsymbol{R_2}$'),

    ('$\\boldsymbol{R_2}$') : ('R'),
    ('$\\boldsymbol{R_2}$', '0') : ('\\=0', 'L', '$\\boldsymbol{R_3}$'),
    ('$\\boldsymbol{R_2}$', '1') : ('\\=1', 'L', '$\\boldsymbol{R_4}$'),
    ('$\\boldsymbol{R_2}$', 'S') : ('S', 'L', '$\\boldsymbol{R_{10}}$'),
    ('$\\boldsymbol{R_2}$', 'Q') : ('Q', 'L', '$\\boldsymbol{R_{10}}$'),
    ('$\\boldsymbol{R_2}$', 'T') : ('T', 'L', '$\\boldsymbol{R_{10}}$'),
    ('$\\boldsymbol{R_2}$', 'Y') : ('Y', 'R', 'accept'),
    ('$\\boldsymbol{R_2}$', 'X') : ('X', 'R', 'reject'),

    ('$\\boldsymbol{R_3}$') : ('L'),
    ('$\\boldsymbol{R_3}$', 'B') : ('B', 'L', '$\\boldsymbol{R_5}$'),

    ('$\\boldsymbol{R_4}$') : ('L'),
    ('$\\boldsymbol{R_4}$', 'B') : ('B', 'L', '$\\boldsymbol{R_6}$'),

    ('$\\boldsymbol{R_5}$') : ('L'),
    ('$\\boldsymbol{R_5}$', '\\=0') : ('\\=0', 'R', '$\\boldsymbol{R_7}$'),
    ('$\\boldsymbol{R_5}$', '\\=1') : ('\\=1', 'R', '$\\boldsymbol{R_7}$'),
    ('$\\boldsymbol{R_5}$', 'q') : ('q', 'R', '$\\boldsymbol{R_7}$'),

    ('$\\boldsymbol{R_6}$') : ('L'),
    ('$\\boldsymbol{R_6}$', '\\=0') : ('\\=0', 'R', '$\\boldsymbol{R_8}$'),
    ('$\\boldsymbol{R_6}$', '\\=1') : ('\\=1', 'R', '$\\boldsymbol{R_8}$'),
    ('$\\boldsymbol{R_6}$', 'q') : ('q', 'R', '$\\boldsymbol{R_8}$'),

    ('$\\boldsymbol{R_7}$', '0') : ('\\=0', 'R', '$\\boldsymbol{R_9}$'),
    ('$\\boldsymbol{R_7}$', '1') : ('\\=0', 'R', '$\\boldsymbol{R_9}$'),

    ('$\\boldsymbol{R_8}$', '0') : ('\\=1', 'R', '$\\boldsymbol{R_9}$'),
    ('$\\boldsymbol{R_8}$', '1') : ('\\=1', 'R', '$\\boldsymbol{R_9}$'),

    ('$\\boldsymbol{R_9}$') : ('R'),
    ('$\\boldsymbol{R_9}$', '\\=q') : ('\\=q', 'R', '$\\boldsymbol{R_2}$'),

    ('$\\boldsymbol{R_{10}}$') : ('L'),
    ('$\\boldsymbol{R_{10}}$', '\\=0') : ('0', 'L', '$\\boldsymbol{R_{10}}$'),
    ('$\\boldsymbol{R_{10}}$', '\\=1') : ('1', 'L', '$\\boldsymbol{R_{10}}$'),
    ('$\\boldsymbol{R_{10}}$', '\\=Q') : ('Q', 'L', '$\\boldsymbol{R_{10}}$'),
    ('$\\boldsymbol{R_{10}}$', '\\=S') : ('S', 'L', '$\\boldsymbol{R_{10}}$'),
    ('$\\boldsymbol{R_{10}}$', '\\=q') : ('q', 'L', '$\\boldsymbol{R_{10}}$'),
    ('$\\boldsymbol{R_{10}}$', 'B') : ('B', 'L', '$\\boldsymbol{Q_0}$'),


    # find and mark the next transition
    ('$\\boldsymbol{Q_0}$') : ('R'),
    ('$\\boldsymbol{Q_0}$', 'Q') : ('\\=Q', 'L', '$\\boldsymbol{Q_1}$'),

    ('$\\boldsymbol{Q_1}$') : ('L'),
    ('$\\boldsymbol{Q_1}$', 'B') : ('B', 'L', '$\\boldsymbol{Q_2}$'),

    ('$\\boldsymbol{Q_2}$') : ('L'),
    ('$\\boldsymbol{Q_2}$', '0') : ('\\=0', 'L', '$\\boldsymbol{Q_2}$'),
    ('$\\boldsymbol{Q_2}$', '1') : ('\\=1', 'L', '$\\boldsymbol{Q_2}$'),
    ('$\\boldsymbol{Q_2}$', 'q') : ('q', 'R', '$\\boldsymbol{Q_3}$'),

    ('$\\boldsymbol{Q_3}$') : ('R'),
    ('$\\boldsymbol{Q_3}$', 'B') : ('B', 'R', '$\\boldsymbol{S}$'),
    ('$\\boldsymbol{Q_3}$', '\\=0') : ('0', 'R', '$\\boldsymbol{Q_4}$'),
    ('$\\boldsymbol{Q_3}$', '\\=1') : ('1', 'R', '$\\boldsymbol{Q_5}$'),

    ('$\\boldsymbol{Q_4}$') : ('R'),
    ('$\\boldsymbol{Q_4}$', '\\=Q') : ('\\=Q', 'R', '$\\boldsymbol{Q_6}$'),

    ('$\\boldsymbol{Q_5}$') : ('R'),
    ('$\\boldsymbol{Q_5}$', '\\=Q') : ('\\=Q', 'R', '$\\boldsymbol{Q_7}$'),

    ('$\\boldsymbol{Q_6}$') : ('R'),
    ('$\\boldsymbol{Q_6}$', '0') : ('\\=0', 'R', '$\\boldsymbol{Q_8}$'),
    ('$\\boldsymbol{Q_6}$', '1') : ('1', 'L', '$\\boldsymbol{Q_{10}}$'),

    ('$\\boldsymbol{Q_7}$') : ('R'),
    ('$\\boldsymbol{Q_7}$', '1') : ('\\=1', 'R', '$\\boldsymbol{Q_8}$'),
    ('$\\boldsymbol{Q_7}$', '0') : ('0', 'L', '$\\boldsymbol{Q_{10}}$'),

    ('$\\boldsymbol{Q_8}$') : ('L'),
    ('$\\boldsymbol{Q_8}$', 'B') : ('B', 'L', '$\\boldsymbol{Q_9}$'),

    ('$\\boldsymbol{Q_9}$') : ('L'),
    ('$\\boldsymbol{Q_9}$', 'q') : ('q', 'R', '$\\boldsymbol{Q_3}$'),

    ('$\\boldsymbol{Q_{10}}$', '\\=0') : ('0', 'L', '$\\boldsymbol{Q_{10}}$'),
    ('$\\boldsymbol{Q_{10}}$', '\\=1') : ('1', 'L', '$\\boldsymbol{Q_{10}}$'),
    ('$\\boldsymbol{Q_{10}}$', '\\=Q') : ('Q', 'R', '$\\boldsymbol{Q_0}$'),
    }

# input is the TM (01)* working on 0101
STARTCONFIG = ( list('q01B11')
                + ['\\=Q']
                + list('01S11Rs01q11S00Rs00q10S01Rs01qX')
                + list('Q10S11Rs11qXS00Rs00qXS01Rs01q01')
                + list('Q11S11Rs11qYS00Rs00qYS01Rs01qY')
                + list( 'T' ) + ['\\=s'] + list( '00s01s00s01' )
                ,0 , '$\\boldsymbol{S}$' )


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:
        try:
            write_symbol = tape[position]
            move = machine[ (state) ]
            next_state = state
        except KeyError:
            print >> sys.stderr, "machine crashed", state, 'on ', tape[position]
            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 += ['$\\Box$']*(position+2-len(tape))

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

    elif move == 'L':
        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] + ["{\\bf "] + [state] + ['}'] + tape[position:] )


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

    print '\\documentclass[a4paper,10pt]{article}'
    print '\\usepackage[a4paper,landscape]{geometry}'
    print '\\usepackage{amssymb}'
    print '\\usepackage{amsmath}'

    #print '\\setlength{\\leftmargin}{0in}'
    #print '\\setlength{\\oddsidemargin}{0in}         % default=0in'
    #print '\\setlength{\\textwidth}{9in}             % default=9in'
    #print '\\setlength{\\textheight}{5.85in}         % default=5.15in'
    #print '\\setlength{\\topmargin}{-0.15in}         % default=0.20in'
    #print '\\setlength{\\headsep}{0.25in}'

    #print '\\title{Universal Turing Machine}'
    print '\\begin{document}'
    #print '\\maketitle'

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

    print '\\ '*6 + config
    print '\\end{document}'