#!/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 Ullman and Hopcroft's UTM
UTM = {
    ('$\\boldsymbol{A}$', '0') : ( '0', 'R', '$\\boldsymbol{A}$' ),
    ('$\\boldsymbol{A}$', '1') : ( '1', 'R', '$\\boldsymbol{A}$' ),
    ('$\\boldsymbol{A}$', 'c') : ( 'c', 'R', '$\\boldsymbol{A}$' ),
    ('$\\boldsymbol{A}$', 'L') : ( 'L', 'R', '$\\boldsymbol{A}$' ),
    ('$\\boldsymbol{A}$', 'R') : ( 'R', 'R', '$\\boldsymbol{A}$' ),
    ('$\\boldsymbol{A}$', '\\=c') : ('\\=c', 'R', '$\\boldsymbol{B}$' ),

    ('$\\boldsymbol{B}$', '0' ): ( '0', 'R', '$\\boldsymbol{B}$' ),
    ('$\\boldsymbol{B}$', '1' ): ( '1', 'R', '$\\boldsymbol{B}$' ),
    ('$\\boldsymbol{B}$', 'c' ): ( 'c', 'R', '$\\boldsymbol{B}$' ),
    ('$\\boldsymbol{B}$', 'L' ): ( 'L', 'R', '$\\boldsymbol{B}$' ),
    ('$\\boldsymbol{B}$', 'R' ): ( 'R', 'R', '$\\boldsymbol{B}$' ),
    ('$\\boldsymbol{B}$', '\\=0') : ('\\=0', 'L', '$\\boldsymbol{C_0}$' ),
    ('$\\boldsymbol{B}$', '\\=1') : ('\\=1', 'L', '$\\boldsymbol{C_1}$' ),
    ('$\\boldsymbol{B}$', '$\\boxdot$') : ('$\\boxdot$', 'L', '$\\boldsymbol{C_B}$' ),

    ('$\\boldsymbol{C_B}$', '0') : ('0', 'L', '$\\boldsymbol{C_B}$'),
    ('$\\boldsymbol{C_B}$', '1') : ('1', 'L', '$\\boldsymbol{C_B}$'),
    ('$\\boldsymbol{C_B}$', 'c') : ('c', 'L', '$\\boldsymbol{C_B}$'),
    ('$\\boldsymbol{C_B}$', 'L') : ('L', 'L', '$\\boldsymbol{C_B}$'),
    ('$\\boldsymbol{C_B}$', 'R') : ('R', 'L', '$\\boldsymbol{C_B}$'),
    ('$\\boldsymbol{C_B}$', '\\=c') : ('c', 'R', '$\\boldsymbol{D_B}$'),

    ('$\\boldsymbol{C_0}$', '0') : ('0', 'L', '$\\boldsymbol{C_0}$'),
    ('$\\boldsymbol{C_0}$', '1') : ('1', 'L', '$\\boldsymbol{C_0}$'),
    ('$\\boldsymbol{C_0}$', 'c') : ('c', 'L', '$\\boldsymbol{C_0}$'),
    ('$\\boldsymbol{C_0}$', 'L') : ('L', 'L', '$\\boldsymbol{C_0}$'),
    ('$\\boldsymbol{C_0}$', 'R') : ('R', 'L', '$\\boldsymbol{C_0}$'),
    ('$\\boldsymbol{C_0}$', '\\=c') : ('c', 'R', '$\\boldsymbol{D_0}$'),

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

    ('$\\boldsymbol{D_B}$', '0') : ('0', 'L', '$\\boldsymbol{V}$'),
    ('$\\boldsymbol{D_B}$', '1') : ('\\=1', 'L', '$\\boldsymbol{E}$'),

    ('$\\boldsymbol{D_0}$', '0') : ('0', 'R', '$\\boldsymbol{D_0}$'),
    ('$\\boldsymbol{D_0}$', '1') : ('1', 'R', '$\\boldsymbol{D_0}$'),
    ('$\\boldsymbol{D_0}$', 'c') : ('c', 'R', '$\\boldsymbol{D_B}$'),
    ('$\\boldsymbol{D_0}$', 'L') : ('L', 'R', '$\\boldsymbol{D_0}$'),
    ('$\\boldsymbol{D_0}$', 'R') : ('R', 'R', '$\\boldsymbol{D_0}$'),

    ('$\\boldsymbol{D_1}$', '0') : ('0', 'R', '$\\boldsymbol{D_1}$'),
    ('$\\boldsymbol{D_1}$', '1') : ('1', 'R', '$\\boldsymbol{D_1}$'),
    ('$\\boldsymbol{D_1}$', 'c') : ('c', 'R', '$\\boldsymbol{D_0}$'),
    ('$\\boldsymbol{D_1}$', 'L') : ('L', 'R', '$\\boldsymbol{D_1}$'),
    ('$\\boldsymbol{D_1}$', 'R') : ('R', 'R', '$\\boldsymbol{D_1}$'),

    ('$\\boldsymbol{E}$', '0') : ('0', 'L', '$\\boldsymbol{E}$'),
    ('$\\boldsymbol{E}$', '1') : ('1', 'L', '$\\boldsymbol{E}$'),
    ('$\\boldsymbol{E}$', 'c') : ('c', 'L', '$\\boldsymbol{F}$'),
    ('$\\boldsymbol{E}$', 'L') : ('L', 'L', '$\\boldsymbol{E}$'),
    ('$\\boldsymbol{E}$', 'R') : ('R', 'L', '$\\boldsymbol{E}$'),

    ('$\\boldsymbol{F}$', '0') : ('0', 'L', '$\\boldsymbol{E}$'),
    ('$\\boldsymbol{F}$', '1') : ('1', 'L', '$\\boldsymbol{E}$'),
    ('$\\boldsymbol{F}$', 'c') : ('c', 'L', '$\\boldsymbol{G}$'),
    ('$\\boldsymbol{F}$', 'L') : ('L', 'L', '$\\boldsymbol{E}$'),
    ('$\\boldsymbol{F}$', 'R') : ('R', 'L', '$\\boldsymbol{E}$'),

    ('$\\boldsymbol{G}$', '0') : ('0', 'L', '$\\boldsymbol{E}$'),
    ('$\\boldsymbol{G}$', '1') : ('1', 'L', '$\\boldsymbol{E}$'),
    ('$\\boldsymbol{G}$', 'c') : ('c', 'R', '$\\boldsymbol{H}$'),
    ('$\\boldsymbol{G}$', 'L') : ('L', 'L', '$\\boldsymbol{E}$'),
    ('$\\boldsymbol{G}$', 'R') : ('R', 'L', '$\\boldsymbol{E}$'),

    ('$\\boldsymbol{H}$', 'c') : ('c', 'R', '$\\boldsymbol{I}$'),

    ('$\\boldsymbol{I}$', 'c') : ('\\=c', 'R', '$\\boldsymbol{J}$'),

    ('$\\boldsymbol{J}$', '0') : ('0', 'R', '$\\boldsymbol{J}$'),
    ('$\\boldsymbol{J}$', '1') : ('1', 'R', '$\\boldsymbol{J}$'),
    ('$\\boldsymbol{J}$', 'c') : ('c', 'R', '$\\boldsymbol{J}$'),
    ('$\\boldsymbol{J}$', 'L') : ('L', 'R', '$\\boldsymbol{J}$'),
    ('$\\boldsymbol{J}$', 'R') : ('R', 'R', '$\\boldsymbol{J}$'),
    ('$\\boldsymbol{J}$', '\\=1') : ('1', 'R', '$\\boldsymbol{K_L}$'),

    ('$\\boldsymbol{K_L}$', '1') : ('\\=1', 'L', '$\\boldsymbol{M_L}$'),
    ('$\\boldsymbol{K_L}$', 'L') : ('L', 'R', '$\\boldsymbol{T_L}$'),
    ('$\\boldsymbol{K_L}$', 'R') : ('R', 'R', '$\\boldsymbol{T_R}$'),

    ('$\\boldsymbol{M_L}$', '0') : ('0', 'L', '$\\boldsymbol{M_L}$'),
    ('$\\boldsymbol{M_L}$', '1') : ('1', 'L', '$\\boldsymbol{M_L}$'),
    ('$\\boldsymbol{M_L}$', 'c') : ('c', 'L', '$\\boldsymbol{M_L}$'),
    ('$\\boldsymbol{M_L}$', 'L') : ('L', 'L', '$\\boldsymbol{M_L}$'),
    ('$\\boldsymbol{M_L}$', 'R') : ('R', 'L', '$\\boldsymbol{M_L}$'),
    ('$\\boldsymbol{M_L}$', '\\=c') : ('c', 'R', '$\\boldsymbol{N_L}$'),

    ('$\\boldsymbol{N_L}$', '0') : ('0', 'R', '$\\boldsymbol{N_L}$'),
    ('$\\boldsymbol{N_L}$', '1') : ('1', 'R', '$\\boldsymbol{N_L}$'),
    ('$\\boldsymbol{N_L}$', 'c') : ('c', 'R', '$\\boldsymbol{P_L}$'),
    ('$\\boldsymbol{N_L}$', 'L') : ('L', 'R', '$\\boldsymbol{N_L}$'),
    ('$\\boldsymbol{N_L}$', 'R') : ('R', 'R', '$\\boldsymbol{N_L}$'),
    ('$\\boldsymbol{N_L}$', '\\=1') : ('\\=1', 'R', '$\\boldsymbol{N_R}$'),

    ('$\\boldsymbol{P_L}$', '0') : ('0', 'R', '$\\boldsymbol{N_L}$'),
    ('$\\boldsymbol{P_L}$', '1') : ('1', 'R', '$\\boldsymbol{N_L}$'),
    ('$\\boldsymbol{P_L}$', 'c') : ('\\=c', 'R', '$\\boldsymbol{S_L}$'),
    ('$\\boldsymbol{P_L}$', 'L') : ('L', 'R', '$\\boldsymbol{N_L}$'),
    ('$\\boldsymbol{P_L}$', 'R') : ('R', 'R', '$\\boldsymbol{N_L}$'),
    ('$\\boldsymbol{P_L}$', '\\=1') : ('\\=1', 'R', '$\\boldsymbol{N_R}$'),

    ('$\\boldsymbol{S_L}$', '0') : ('0', 'R', '$\\boldsymbol{S_L}$'),
    ('$\\boldsymbol{S_L}$', '1') : ('1', 'R', '$\\boldsymbol{S_L}$'),
    ('$\\boldsymbol{S_L}$', 'c') : ('c', 'R', '$\\boldsymbol{S_L}$'),
    ('$\\boldsymbol{S_L}$', 'L') : ('L', 'R', '$\\boldsymbol{S_L}$'),
    ('$\\boldsymbol{S_L}$', 'R') : ('R', 'R', '$\\boldsymbol{S_L}$'),
    ('$\\boldsymbol{S_L}$', '\\=1') : ('1', 'R', '$\\boldsymbol{K_L}$'),

    ('$\\boldsymbol{K_R}$', '1') : ('\\=1', 'R', '$\\boldsymbol{M_R}$'),
    ('$\\boldsymbol{K_R}$', 'L') : ('L', 'R', '$\\boldsymbol{T_L}$'),
    ('$\\boldsymbol{K_R}$', 'R') : ('R', 'R', '$\\boldsymbol{T_R}$'),

    ('$\\boldsymbol{M_R}$', '0') : ('0', 'R', '$\\boldsymbol{M_R}$'),
    ('$\\boldsymbol{M_R}$', '1') : ('1', 'R', '$\\boldsymbol{M_R}$'),
    ('$\\boldsymbol{M_R}$', 'c') : ('c', 'R', '$\\boldsymbol{M_R}$'),
    ('$\\boldsymbol{M_R}$', 'L') : ('L', 'R', '$\\boldsymbol{M_R}$'),
    ('$\\boldsymbol{M_R}$', 'R') : ('R', 'R', '$\\boldsymbol{M_R}$'),
    ('$\\boldsymbol{M_R}$', '\\=c') : ('c', 'R', '$\\boldsymbol{N_R}$'),

    ('$\\boldsymbol{N_R}$', '0') : ('0', 'R', '$\\boldsymbol{N_R}$'),
    ('$\\boldsymbol{N_R}$', '1') : ('1', 'R', '$\\boldsymbol{N_R}$'),
    ('$\\boldsymbol{N_R}$', 'c') : ('c', 'R', '$\\boldsymbol{P_R}$'),
    ('$\\boldsymbol{N_R}$', 'L') : ('L', 'R', '$\\boldsymbol{N_R}$'),
    ('$\\boldsymbol{N_R}$', 'R') : ('R', 'R', '$\\boldsymbol{N_R}$'),

    ('$\\boldsymbol{P_R}$', '0') : ('0', 'R', '$\\boldsymbol{N_R}$'),
    ('$\\boldsymbol{P_R}$', '1') : ('1', 'R', '$\\boldsymbol{N_R}$'),
    ('$\\boldsymbol{P_R}$', 'c') : ('\\=c', 'L', '$\\boldsymbol{S_R}$'),
    ('$\\boldsymbol{P_R}$', 'L') : ('L', 'R', '$\\boldsymbol{N_R}$'),
    ('$\\boldsymbol{P_R}$', 'R') : ('R', 'R', '$\\boldsymbol{N_R}$'),

    ('$\\boldsymbol{S_R}$', '0') : ('0', 'L', '$\\boldsymbol{S_R}$'),
    ('$\\boldsymbol{S_R}$', '1') : ('1', 'L', '$\\boldsymbol{S_R}$'),
    ('$\\boldsymbol{S_R}$', 'c') : ('c', 'L', '$\\boldsymbol{S_R}$'),
    ('$\\boldsymbol{S_R}$', 'L') : ('L', 'L', '$\\boldsymbol{S_R}$'),
    ('$\\boldsymbol{S_R}$', 'R') : ('R', 'L', '$\\boldsymbol{S_R}$'),
    ('$\\boldsymbol{S_R}$', '\\=1') : ('1', 'R', '$\\boldsymbol{K_R}$'),

    ('$\\boldsymbol{T_L}$', '0') : ('0', 'R', '$\\boldsymbol{T_{L_0}}$'),
    ('$\\boldsymbol{T_L}$', '1') : ('1', 'R', '$\\boldsymbol{T_{L_1}}$'),

    ('$\\boldsymbol{T_R}$', '0') : ('0', 'R', '$\\boldsymbol{T_{R_0}}$'),
    ('$\\boldsymbol{T_R}$', '1') : ('1', 'R', '$\\boldsymbol{T_{R_1}}$'),

    ('$\\boldsymbol{T_{L_0}}$', '0') : ('0', 'R', '$\\boldsymbol{T_{L_0}}$'),
    ('$\\boldsymbol{T_{L_0}}$', '1') : ('1', 'R', '$\\boldsymbol{T_{L_0}}$'),
    ('$\\boldsymbol{T_{L_0}}$', 'c') : ('c', 'R', '$\\boldsymbol{T_{L_0}}$'),
    ('$\\boldsymbol{T_{L_0}}$', 'L') : ('L', 'R', '$\\boldsymbol{T_{L_0}}$'),
    ('$\\boldsymbol{T_{L_0}}$', 'R') : ('R', 'R', '$\\boldsymbol{T_{L_0}}$'),
    ('$\\boldsymbol{T_{L_0}}$', '\\=0') : ('0', 'L', '$\\boldsymbol{U}$'),
    ('$\\boldsymbol{T_{L_0}}$', '\\=1') : ('0', 'L', '$\\boldsymbol{U}$'),
    ('$\\boldsymbol{T_{L_0}}$', '\\=c') : ('\\=c', 'R', '$\\boldsymbol{T_{L_0}}$'),
    ('$\\boldsymbol{T_{L_0}}$', '$\\boxdot$') : ('0', 'L', '$\\boldsymbol{U}$'),

    ('$\\boldsymbol{T_{L_1}}$', '0') : ('0', 'R', '$\\boldsymbol{T_{L_1}}$'),
    ('$\\boldsymbol{T_{L_1}}$', '1') : ('1', 'R', '$\\boldsymbol{T_{L_1}}$'),
    ('$\\boldsymbol{T_{L_1}}$', 'c') : ('c', 'R', '$\\boldsymbol{T_{L_1}}$'),
    ('$\\boldsymbol{T_{L_1}}$', 'L') : ('L', 'R', '$\\boldsymbol{T_{L_1}}$'),
    ('$\\boldsymbol{T_{L_1}}$', 'R') : ('R', 'R', '$\\boldsymbol{T_{L_1}}$'),
    ('$\\boldsymbol{T_{L_1}}$', '\\=0') : ('1', 'L', '$\\boldsymbol{U}$'),
    ('$\\boldsymbol{T_{L_1}}$', '\\=1') : ('1', 'L', '$\\boldsymbol{U}$'),
    ('$\\boldsymbol{T_{L_1}}$', '\\=c') : ('\\=c', 'R', '$\\boldsymbol{T_{L_1}}$'),
    ('$\\boldsymbol{T_{L_1}}$', '$\\boxdot$') : ('1', 'L', '$\\boldsymbol{U}$'),

    ('$\\boldsymbol{T_{R_0}}$', '0') : ('0', 'R', '$\\boldsymbol{T_{R_0}}$'),
    ('$\\boldsymbol{T_{R_0}}$', '1') : ('1', 'R', '$\\boldsymbol{T_{R_0}}$'),
    ('$\\boldsymbol{T_{R_0}}$', 'c') : ('c', 'R', '$\\boldsymbol{T_{R_0}}$'),
    ('$\\boldsymbol{T_{R_0}}$', 'L') : ('L', 'R', '$\\boldsymbol{T_{R_0}}$'),
    ('$\\boldsymbol{T_{R_0}}$', 'R') : ('R', 'R', '$\\boldsymbol{T_{R_0}}$'),
    ('$\\boldsymbol{T_{R_0}}$', '\\=0') : ('0', 'R', '$\\boldsymbol{U}$'),
    ('$\\boldsymbol{T_{R_0}}$', '\\=1') : ('0', 'R', '$\\boldsymbol{U}$'),
    ('$\\boldsymbol{T_{R_0}}$', '\\=c') : ('\\=c', 'R', '$\\boldsymbol{T_{R_0}}$'),
    ('$\\boldsymbol{T_{R_0}}$', '$\\boxdot$') : ('0', 'R', '$\\boldsymbol{U}$'),

    ('$\\boldsymbol{T_{R_1}}$', '0') : ('0', 'R', '$\\boldsymbol{T_{R_1}}$'),
    ('$\\boldsymbol{T_{R_1}}$', '1') : ('1', 'R', '$\\boldsymbol{T_{R_1}}$'),
    ('$\\boldsymbol{T_{R_1}}$', 'c') : ('c', 'R', '$\\boldsymbol{T_{R_1}}$'),
    ('$\\boldsymbol{T_{R_1}}$', 'L') : ('L', 'R', '$\\boldsymbol{T_{R_1}}$'),
    ('$\\boldsymbol{T_{R_1}}$', 'R') : ('R', 'R', '$\\boldsymbol{T_{R_1}}$'),
    ('$\\boldsymbol{T_{R_1}}$', '\\=0') : ('1', 'R', '$\\boldsymbol{U}$'),
    ('$\\boldsymbol{T_{R_1}}$', '\\=1') : ('1', 'R', '$\\boldsymbol{U}$'),
    ('$\\boldsymbol{T_{R_1}}$', '\\=c') : ('\\=c', 'R', '$\\boldsymbol{T_{R_1}}$'),
    ('$\\boldsymbol{T_{R_1}}$', '$\\boxdot$') : ('1', 'R', '$\\boldsymbol{U}$'),

    ('$\\boldsymbol{U}$', '0') : ('\\=0', 'L', '$\\boldsymbol{C_0}$'),
    ('$\\boldsymbol{U}$', '1') : ('\\=1', 'L', '$\\boldsymbol{C_1}$'),
    ('$\\boldsymbol{U}$', '$\\Box$') : ('$\\boxdot$', 'L', '$\\boldsymbol{C_B}$'),

    ('$\\boldsymbol{V}$', '0') : ('0', 'L', '$\\boldsymbol{V}$'),
    ('$\\boldsymbol{V}$', '1') : ('1', 'L', '$\\boldsymbol{V}$'),
    ('$\\boldsymbol{V}$', 'c') : ('c', 'L', '$\\boldsymbol{W}$'),
    ('$\\boldsymbol{V}$', 'L') : ('L', 'L', '$\\boldsymbol{V}$'),
    ('$\\boldsymbol{V}$', 'R') : ('R', 'L', '$\\boldsymbol{V}$'),

    ('$\\boldsymbol{W}$', '0') : ('0', 'L', '$\\boldsymbol{V}$'),
    ('$\\boldsymbol{W}$', '1') : ('1', 'L', '$\\boldsymbol{V}$'),
    ('$\\boldsymbol{W}$', 'c') : ('c', 'R', '$\\boldsymbol{X_1}$'),
    ('$\\boldsymbol{W}$', 'L') : ('L', 'L', '$\\boldsymbol{V}$'),
    ('$\\boldsymbol{W}$', 'R') : ('R', 'L', '$\\boldsymbol{V}$'),

    ('$\\boldsymbol{X_1}$', 'c') : ('c', 'R', '$\\boldsymbol{X_2}$'),
    ('$\\boldsymbol{X_2}$', '0') : ('0', 'R', '$\\boldsymbol{X_3}$'),
    ('$\\boldsymbol{X_3}$', 'c') : ('c', 'R', '$\\boldsymbol{X_4}$'),
    ('$\\boldsymbol{X_4}$', '0') : ('0', 'R', '$\\boldsymbol{X_5}$'),
    ('$\\boldsymbol{X_5}$', 'c') : ('c', 'R', '$\\boldsymbol{X_6}$'),
    ('$\\boldsymbol{X_6}$', '0') : ('0', 'R', 'accept')
    }

STARTCONFIG = ( list('cc') + ['\\=c'] + list('111R1c11R0c0cc0c0c1R1cc0c0c0ccc') + ['\\=0'] + list('10101'), 0, '$\\boldsymbol{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:
        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{amssymb}'
    print '\\usepackage{amsmath}'
    print '\\usepackage{vaucanson-g}'
    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}'