def run(transitions, input, steps):
    """simulate Turing machine for the given number of steps and the given input"""

    # convert input from string to list of symbols
    # we use '|>' as a symbol to indicate the beginning of the tape
    input = ['|>'] + list(input) + [' ']

    # sanitize transitions for 'accept' and 'reject' states and for symbol '|>'
    transitions = sanitize_transitions(transitions)

    # create initial configuration
    c = Configuration(state='start', head=1, tape=input)

    for i in range(0, steps):
        # read tape content under head
        current = c.state
        read = c.tape[c.head]

        # lookup transition based on state and read symbol
        next, write, move = transitions(current, read)

        # update configuration
        c.state = next
        c.tape[c.head] = write
        c.head += move
        if c.head >= len(c.tape):
            c.tape += [' ']

    # return final configuration
    return c


"""
Explanation: Turing machine computation
Tape
We will represent the tape as a list of tape symbols and we will represent tape symbols as Python strings.
The string ' ' represents the blank symbol.
The string '|&gt;' represents the start symbol, which indicates the beginning of the tape.
States
We will also encode states as Python strings. 
The string 'start' represents that start state.
The strings 'accept', 'reject', and 'halt' represent final states of the machine, that indicate acceptance, rejection, and halting, respectively. 
Simulation
The following function simulates a given Turing machine for a given number of steps on a given input
End of explanation
"""


def check_transitions(transitions, states, alphabet):

    transitions = sanitize_transitions(transitions)

    for current in states:
        for read in alphabet:
            next, write, move = transitions(current, read)

            # we either stay in place or move one position
            # to the left or right
            assert(move in [-1,0,1])

            # if we read the begin symbol,
            if read == '|>':
                # we need to write it back
                assert(write == '|>')
                # we need to move to the right
                assert(move == 1)
            else:
                # we cannot write the begin symbol
                assert(write != '|>')

            # if we are in one of the final states
            if current in ['accept', 'reject', 'halt']:
                # we cannot change to a different state
                assert(next == current)

    print("transition checks passed")


"""
Explanation: The following function checks that the transition functions satisfies some simple syntactic requirements (don't move to the left of the start symbol, don't remove or add start symbols, don't change state after accepting, rejecting, or halting.)
End of explanation
"""


def transitions_copy(current, read):
    if read == '|>':
        return 'start', read, 1
    elif current == 'start':
        if 'write' not in read:
            return read + '-write', read + '-read', 1
        else:
            return 'accept', read, 1
    elif 'write' in current:
        if read != ' ':
            return current, read, 1
        else:
            return 'rewind', current, -1
    elif current == 'rewind':
        if 'read' not in read:
            return current, read, -1
        else:
            return 'start', read, 1

"""
Explanation: Examples
Copy machine
The following Turing machine copies its input, i.e., it computes the function $f(x)=xx$. 
The actual implementation uses different versions of the '0' and '1' symbol (called '0-read', '0-write' and '1-read', '1-write') in the two copies of the string $x$.
We could replace those by regular '0' and '1' symbols by sweeping once more over the tape before the end of the computation.
End of explanation
"""


transitions_table(transitions_copy, 
                  ['start', '0-write', '1-write', 'rewind'],
                  ['0', '1', '0-read', '1-read', '0-write', '1-write'])

"""
Explanation: Here is the full transitions function table of the machine:
End of explanation
"""


simulate(transitions_copy, input='10011', unary=False)

"""
Explanation: Here is an interactive simulation of the copy Turing machine (requires that ipython notebook is run locally).
You can either click on the simulate button to view the computation during a given range of steps or you can drag the current step slider to view the configuration of the machine at a particular step. (If you click on the current step slider, you can also change it using the arrow keys.)
End of explanation
"""


def transitions_power(current,read):
    if read == '|>':
        return 'start', read, 1;
    elif current == 'rewind':
        return current, read, -1
    elif read == 'x':
        return current, read, 1  
    elif current == 'start':
        if read != '1':
            return 'reject', read, 1
        else: 
            return 'start-even', read, 1
    elif 'even' in current and read == '1':
        return 'odd', 'x', 1
    elif current == 'odd' and read == '1':
        return 'even', read, 1
    elif current == 'odd':
        if read == ' ':
            return 'rewind', '2', -1
        else:
            return current, read, 1
    elif current == 'start-even' and read != '1':
        return 'accept', read, -1
    elif current == 'even' and read != '1':
        return 'reject', read, -1

"""
Explanation: Power-of-2 machine
The following Turing machine determines if the input is the unary encoding of a power of 2.
Furthermore, given any string $1^n$, it outputs a string of the form ${0,1}^n2^i$, where $i$ is the largest number such that $2^i$ divides $n$.
End of explanation
"""


transitions_table(transitions_power, 
                  ['start', 'start-even', 'even', 'odd', 'rewind'], 
                  ['0', '1', 'x', ' ', '|>'])

"""
Explanation: Here is the full transition function table of the Turing machine:
End of explanation
"""


simulate(transitions_power, input_unary=16, step_to=200, unary=True)

"""
Explanation: Here is an interactive simulation of the power Turing machine (requires that ipython notebook is run locally).
You can either click on the simulate button to view the computation during a given range of steps or you can drag the current step slider to view the configuration of the machine at a particular step.
(If you click on the current step slider, you can also change it using the arrow keys.)
End of explanation
"""


