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
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.)
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]:
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.)
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]:
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.)
In [9]:
simulate(transitions_power, input_unary=16, step_to=200, unary=True)
In [ ]: