```
In [1]:
```%run -i turing.py
init()

```
```

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 `'|>'`

represents the *start symbol*, which indicates the beginning of the tape.

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.

The following function simulates a given Turing machine for a given number of steps on a given input

```
In [2]:
```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

```
In [3]:
```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")

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.

```
In [4]:
```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

Here is the full transitions function table of the machine:

```
In [5]:
```transitions_table(transitions_copy,
['start', '0-write', '1-write', 'rewind'],
['0', '1', '0-read', '1-read', '0-write', '1-write'])

```
Out[5]:
```

`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.)

```
In [6]:
```simulate(transitions_copy, input='10011', unary=False)

```
```

```
In [7]:
```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

Here is the full transition function table of the Turing machine:

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

```
Out[8]:
```

`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.)

```
In [9]:
```simulate(transitions_power, input_unary=16, step_to=200, unary=True)

```
```

```
In [ ]:
```