Turing Machines in Action
October 7th, 2007
In this post I will define turing machines and demonstrate a simple one in action.
Definition of a Turing Machine
A turing machine (TM) description consists of a tuple of 7 objects: a set of states Q, an input alphabet I, a tape alphabet T, a transition function F, a set of accept states Qaccept, a set of reject states Qreject and a start state Qstart.
The following requirements must hold: I is contained in T. ‘ ‘ (the space symbol) is a member of T but not of I. F is a function from QxT->QxTx{1,-1}. Qaccept and Qreject are disjoint subsets of Q. Qstart is a member of Q.
The turing machine itself consists of: its description (as defined above), an infinite tape, a head and a current state.
The tape is an infinite list of symbols from T (it is only infinite to the right, i.e. it has indexes 0, 1, 2, … but no negative indexes). The tape initially contains the input (a string of symbols from I) starting at index 0 followed by infinitely many ’ ‘ (space) symbols. As we required that the ‘ ‘ symbol is not a member of I the TM can detect the end of the input.
The head is simply a pointer to the tape. It initially points to tape position 0.
The current state is a member of Q, and is initialized to Qstart.
Operation
A TM with a description {Q, I, T, F, Qaccept, Qreject, Qstart} is initialized as indicated above. The result of its operation consists of the contents of the tape as well as an additional flag which can be either ACCEPT or REJECT. In the description below, the action accept means setting this flag to the ACCEPT state and halting. The same goes for the reject action.
The TM operates as follows:
- If current_state is in Qaccept, accept. If it is in Qreject, reject.
- Read a symbol from the tape at the position indicated by the head. Denote it as current_symbol.
- Set next_state, next_symbol, next_head_pos to F(current_state, current_symbol).
- Write next_symbol to the tape at the current head position.
- If next_head_pos is 1 move the head one position to the right.
- If next_head_pos is -1 move the head one position to the left. If the head tries to move to the left from position 0, do not move the head.
- Set current_state to next_state.
And that’s it!
An Example
The following is the description of a TM that multiplies two integers in unary notation. For example, if its input is of the form ’111*11=’ it will accept with an output tape of ’111*11=111111′.
The code of the machine:
TMUnaryMultiply = {
'description' : """The input must be of the form '11*111='. The output tape will look like '11*111=111111'.""",
'start_state' : 'mark_start',
#input verification
'mark_start' :
{
'1':['verify_input_1','#',1],
},
'verify_input_1' :
{
'1':['verify_input_1','1',1],
'*':['verify_input_*','*',1]
},
'verify_input_*' :
{
'1':['verify_input_2','1',1]
},
'verify_input_2' :
{
'1':['verify_input_2','1',1],
'=':['verify_input_ ','=',1]
},
'verify_input_ ' :
{
' ':['move_head_to_left',' ',-1]
},
'move_head_to_left':
{
'1':['move_head_to_left','1',-1],
'=':['move_head_to_left','=',-1],
'*':['move_head_to_left','*',-1],
'#':['read_ones','1',-1] # this will try to move the head off the tape
},
# actual multiplication
'read_ones' :
{
'1':['wait_for_*', '#', 1],
'*':['halt','*', -1],
},
'wait_for_*' :
{
'1':['wait_for_*', '1', 1],
'*':['copy_ones', '*', 1]
},
'copy_ones' :
{
'1':['wait_for_=', '#', 1],
'=':['move_left2','=', -1],
},
'wait_for_=' :
{
'1':['wait_for_=','1',1],
'=':['wait_for_ ','=',1]
},
'wait_for_ ' :
{
'1':['wait_for_ ','1',1],
' ':['move_left','1',-1]
},
'move_left':
{
'1':['move_left','1',-1],
'=':['move_left','=',-1],
'#':['copy_ones','1', 1]
},
'move_left2':
{
'1':['move_left2','1',-1],
'*':['move_left2','*',-1],
'#':['read_ones','1', 1]
},
'halt' : {}
}
I think the format of the description is self explanatory (for the python connoisseurs among you, it consists of some nested dictionaries). It can be fed into my Python TM Emulator (the code of which is included at the end of this article). The emulator can also automatically generate a flow graph of the TM. Here is a sample ouput:
Running the emulator (in verbose mode) with the TMUnaryMultiply description above on the input ’111*11=’ results in the following:
Initialing TM [The input must be of the form '11*111='. The output tape will look like '11*111=111111'.]...
Running tm with input [111*11=]...
V
< mark_start>: ['1', '1', '1', '*', '1', '1', '=', ' ']
V
< verify_input_1>: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< verify_input_1>: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< verify_input_1>: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< verify_input_*>: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< verify_input_2>: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< verify_input_2>: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< verify_input_ >: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< move_head_to_left>: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< move_head_to_left>: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< move_head_to_left>: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< move_head_to_left>: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< move_head_to_left>: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< move_head_to_left>: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< move_head_to_left>: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< read_ones>: ['1', '1', '1', '*', '1', '1', '=', ' ']
V
< wait_for_*>: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< wait_for_*>: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< wait_for_*>: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< copy_ones>: ['#', '1', '1', '*', '1', '1', '=', ' ']
V
< wait_for_=>: ['#', '1', '1', '*', '#', '1', '=', ' ']
V
< wait_for_=>: ['#', '1', '1', '*', '#', '1', '=', ' ']
V
< wait_for_ >: ['#', '1', '1', '*', '#', '1', '=', ' ']
V
< move_left>: ['#', '1', '1', '*', '#', '1', '=', '1']
V
< move_left>: ['#', '1', '1', '*', '#', '1', '=', '1']
V
< move_left>: ['#', '1', '1', '*', '#', '1', '=', '1']
V
< copy_ones>: ['#', '1', '1', '*', '1', '1', '=', '1']
V
< wait_for_=>: ['#', '1', '1', '*', '1', '#', '=', '1']
V
< wait_for_ >: ['#', '1', '1', '*', '1', '#', '=', '1']
V
< wait_for_ >: ['#', '1', '1', '*', '1', '#', '=', '1', ' ']
V
< move_left>: ['#', '1', '1', '*', '1', '#', '=', '1', '1']
V
< move_left>: ['#', '1', '1', '*', '1', '#', '=', '1', '1']
V
< move_left>: ['#', '1', '1', '*', '1', '#', '=', '1', '1']
V
< copy_ones>: ['#', '1', '1', '*', '1', '1', '=', '1', '1']
V
< move_left2>: ['#', '1', '1', '*', '1', '1', '=', '1', '1']
V
< move_left2>: ['#', '1', '1', '*', '1', '1', '=', '1', '1']
V
< move_left2>: ['#', '1', '1', '*', '1', '1', '=', '1', '1']
V
< move_left2>: ['#', '1', '1', '*', '1', '1', '=', '1', '1']
V
< move_left2>: ['#', '1', '1', '*', '1', '1', '=', '1', '1']
V
< move_left2>: ['#', '1', '1', '*', '1', '1', '=', '1', '1']
V
< read_ones>: ['1', '1', '1', '*', '1', '1', '=', '1', '1']
V
< wait_for_*>: ['1', '#', '1', '*', '1', '1', '=', '1', '1']
V
< wait_for_*>: ['1', '#', '1', '*', '1', '1', '=', '1', '1']
V
< copy_ones>: ['1', '#', '1', '*', '1', '1', '=', '1', '1']
V
< wait_for_=>: ['1', '#', '1', '*', '#', '1', '=', '1', '1']
V
< wait_for_=>: ['1', '#', '1', '*', '#', '1', '=', '1', '1']
V
< wait_for_ >: ['1', '#', '1', '*', '#', '1', '=', '1', '1']
V
< wait_for_ >: ['1', '#', '1', '*', '#', '1', '=', '1', '1']
V
< wait_for_ >: ['1', '#', '1', '*', '#', '1', '=', '1', '1', ' ']
V
< move_left>: ['1', '#', '1', '*', '#', '1', '=', '1', '1', '1']
V
< move_left>: ['1', '#', '1', '*', '#', '1', '=', '1', '1', '1']
V
< move_left>: ['1', '#', '1', '*', '#', '1', '=', '1', '1', '1']
V
< move_left>: ['1', '#', '1', '*', '#', '1', '=', '1', '1', '1']
V
< move_left>: ['1', '#', '1', '*', '#', '1', '=', '1', '1', '1']
V
< copy_ones>: ['1', '#', '1', '*', '1', '1', '=', '1', '1', '1']
V
< wait_for_=>: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1']
V
< wait_for_ >: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1']
V
< wait_for_ >: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1']
V
< wait_for_ >: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1']
V
< wait_for_ >: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1', ' ']
V
< move_left>: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1', '1']
V
< move_left>: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1', '1']
V
< move_left>: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1', '1']
V
< move_left>: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1', '1']
V
< move_left>: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1', '1']
V
< copy_ones>: ['1', '#', '1', '*', '1', '1', '=', '1', '1', '1', '1']
V
< move_left2>: ['1', '#', '1', '*', '1', '1', '=', '1', '1', '1', '1']
V
< move_left2>: ['1', '#', '1', '*', '1', '1', '=', '1', '1', '1', '1']
V
< move_left2>: ['1', '#', '1', '*', '1', '1', '=', '1', '1', '1', '1']
V
< move_left2>: ['1', '#', '1', '*', '1', '1', '=', '1', '1', '1', '1']
V
< move_left2>: ['1', '#', '1', '*', '1', '1', '=', '1', '1', '1', '1']
V
< read_ones>: ['1', '1', '1', '*', '1', '1', '=', '1', '1', '1', '1']
V
< wait_for_*>: ['1', '1', '#', '*', '1', '1', '=', '1', '1', '1', '1']
V
< copy_ones>: ['1', '1', '#', '*', '1', '1', '=', '1', '1', '1', '1']
V
< wait_for_=>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1']
V
< wait_for_=>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1']
V
< wait_for_ >: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1']
V
< wait_for_ >: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1']
V
< wait_for_ >: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1']
V
< wait_for_ >: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1']
V
< wait_for_ >: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1', ' ']
V
< move_left>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1', '1']
V
< move_left>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1', '1']
V
< move_left>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1', '1']
V
< move_left>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1', '1']
V
< move_left>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1', '1']
V
< move_left>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1', '1']
V
< move_left>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1', '1']
V
< copy_ones>: ['1', '1', '#', '*', '1', '1', '=', '1', '1', '1', '1', '1']
V
< wait_for_=>: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1']
V
< wait_for_ >: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1']
V
< wait_for_ >: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1']
V
< wait_for_ >: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1']
V
< wait_for_ >: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1']
V
< wait_for_ >: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1']
V
< wait_for_ >: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1', ' ']
V
< move_left>: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1', '1']
V
< move_left>: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1', '1']
V
< move_left>: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1', '1']
V
< move_left>: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1', '1']
V
< move_left>: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1', '1']
V
< move_left>: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1', '1']
V
< move_left>: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1', '1']
V
< copy_ones>: ['1', '1', '#', '*', '1', '1', '=', '1', '1', '1', '1', '1', '1']
V
< move_left2>: ['1', '1', '#', '*', '1', '1', '=', '1', '1', '1', '1', '1', '1']
V
< move_left2>: ['1', '1', '#', '*', '1', '1', '=', '1', '1', '1', '1', '1', '1']
V
< move_left2>: ['1', '1', '#', '*', '1', '1', '=', '1', '1', '1', '1', '1', '1']
V
< move_left2>: ['1', '1', '#', '*', '1', '1', '=', '1', '1', '1', '1', '1', '1']
V
< read_ones>: ['1', '1', '1', '*', '1', '1', '=', '1', '1', '1', '1', '1', '1']
accept
Finally, here is the code of my Python TM Emulator:
class TM:
def __init__(self, states, accept_states, reject_states):
print 'Initialing TM [%s]...' % (states['description'])
self.states = states
self.accept_states = accept_states
self.reject_states = reject_states
self.halt_states = accept_states + reject_states
def run(self, input,verbose=False):
head_pos = 0
current = self.states['start_state']
tape = [x for x in input]+[" "]
while current not in self.halt_states:
if verbose:
print ' '*(22+1+1+1+5*(head_pos)+1)+'V'
print '<%20s>: %s' % (current, tape)
try:
next_state, next_symbol, head_movement = self.states[current][tape[head_pos]]
except KeyError:
return "reject"
tape[head_pos] = next_symbol
head_pos += head_movement
if head_pos < 0:
head_pos = 0
elif head_pos == len(tape):
tape.append(" ")
current = next_state
print ''.join(tape)
if current in self.accept_states:
return 'accept'
else:
assert(current in self.reject_states)
return 'reject'
And that of a simple test method:
def test():
mul = TM(TMUnaryMultiply, ["halt"], [""])
inputs = ['bad_input','111*11=','1*1=','*1=','1*=','11111111*1111111=']
for input in inputs:
print 'Running tm with input [%s]...' % (input)
print mul.run(input)
A sample output:
>>> test()
Initialing TM [The input must be of the form '11*111='. The output tape will look like '11*111=111111'.]...
Running tm with input [bad_input]...
reject
Running tm with input [111*11=]...
111*11=111111
accept
Running tm with input [1*1=]...
1*1=1
accept
Running tm with input [*1=]...
reject
Running tm with input [1*=]...
reject
Running tm with input [11111111*1111111=]...
11111111*1111111=11111111111111111111111111111111111111111111111111111111
accept
A second, more interesting TM performs binary addition:
TMBinaryAddReverse = {
'description' : """The input must be of the form '1010+0010=' (i.e. in reversed binary notation, operands of same size padded with an extra 0). The output will look like '1010+0010=1110'.""",
'start_state' : 'mark_start_carry_0',
'halt': {},
'mark_start_carry_0' :
{
'1':['sum_1','#',1],
'0':['sum_0','#',1],
'+':['halt','+',1]
},
'mark_start_carry_1' :
{
'1':['sum_2','#',1],
'0':['sum_1','#',1],
'+':['halt','+',1]
},
'sum_0' :
{
'1':['sum_0','1',1],
'0':['sum_0','0',1],
'+':['sum_0_get_next','+',1],
'=':['write_0','=',1],
},
'sum_1' :
{
'1':['sum_1','1',1],
'0':['sum_1','0',1],
'+':['sum_1_get_next','+',1],
'=':['write_1','=',1],
},
'sum_2' :
{
'1':['sum_2','1',1],
'0':['sum_2','0',1],
'+':['sum_2_get_next','+',1],
'=':['write_2','=',1],
},
'sum_3' :
{
'1':['sum_3','1',1],
'0':['sum_3','0',1],
'=':['write_3','=',1],
},
'sum_1_get_next':
{
'#':['sum_1_get_next','#',1],
'1':['sum_2','#',1],
'0':['sum_1','#',1],
},
'sum_0_get_next':
{
'#':['sum_0_get_next','#',1],
'1':['sum_1','#',1],
'0':['sum_0','#',1],
},
'sum_2_get_next':
{
'#':['sum_2_get_next','#',1],
'1':['sum_3','#',1],
'0':['sum_2','#',1],
},
'write_0':
{
'1':['write_0','1',1],
'0':['write_0','0',1],
' ':['move_left_carry_0','0',-1],
},
'write_1':
{
'1':['write_1','1',1],
'0':['write_1','0',1],
' ':['move_left_carry_0','1',-1],
},
'write_2':
{
'1':['write_2','1',1],
'0':['write_2','0',1],
' ':['move_left_carry_1','0',-1],
},
'write_3':
{
'1':['write_3','1',1],
'0':['write_3','0',1],
' ':['move_left_carry_1','1',-1],
},
'move_left_carry_0':
{
'0':['move_left_carry_0','0',-1],
'1':['move_left_carry_0','1',-1],
'=':['move_left_carry_0','=',-1],
'#':['move_left_carry_0','#',-1],
'+':['move_left_carry_0_part_2','+',-1],
},
'move_left_carry_1':
{
'0':['move_left_carry_1','0',-1],
'1':['move_left_carry_1','1',-1],
'=':['move_left_carry_1','=',-1],
'#':['move_left_carry_1','#',-1],
'+':['move_left_carry_1_part_2','+',-1],
},
'move_left_carry_0_part_2':
{
'0':['move_left_carry_0_part_2','0',-1],
'1':['move_left_carry_0_part_2','1',-1],
'#':['mark_start_carry_0','#',1],
},
'move_left_carry_1_part_2':
{
'0':['move_left_carry_1_part_2','0',-1],
'1':['move_left_carry_1_part_2','1',-1],
'#':['mark_start_carry_1','#',1],
},
}
Its graph is included here for your convenience (click to enlarge):
And a sample run:
>>> mul = TM(TMBinaryAddReverse, ["halt"], [])
Initialing TM [The input must be of the form '1010+0010=' (i.e. in reversed binary notation, operands of same size padded with an extra 0). The output will look like '1010+0010=1110'.]...
>>> mul.run('1110+1100=',True)
V
<mark_start_carry_0> : ['1', '1', '1', '0', '+', '1', '1', '0', '0', '=', ' ']
V
<sum_1> : ['#', '1', '1', '0', '+', '1', '1', '0', '0', '=', ' ']
V
<sum_1> : ['#', '1', '1', '0', '+', '1', '1', '0', '0', '=', ' ']
V
<sum_1> : ['#', '1', '1', '0', '+', '1', '1', '0', '0', '=', ' ']
V
<sum_1> : ['#', '1', '1', '0', '+', '1', '1', '0', '0', '=', ' ']
V
<sum_1_get_next> : ['#', '1', '1', '0', '+', '1', '1', '0', '0', '=', ' ']
V
<sum_2> : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', ' ']
V
<sum_2> : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', ' ']
V
<sum_2> : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', ' ']
V
<sum_2> : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', ' ']
V
<write_2> : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', ' ']
V
<move_left_carry_1> : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
V
<move_left_carry_1> : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
V
<move_left_carry_1> : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
V
<move_left_carry_1> : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
V
<move_left_carry_1> : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
V
<move_left_carry_1> : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
V
<move_left_carry_1_part_2> : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
V
<move_left_carry_1_part_2> : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
V
<move_left_carry_1_part_2> : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
V
<move_left_carry_1_part_2> : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
V
<mark_start_carry_1> : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
V
<sum_2> : ['#', '#', '1', '0', '+', '#', '1', '0', '0', '=', '0']
V
<sum_2> : ['#', '#', '1', '0', '+', '#', '1', '0', '0', '=', '0']
V
<sum_2> : ['#', '#', '1', '0', '+', '#', '1', '0', '0', '=', '0']
V
<sum_2_get_next> : ['#', '#', '1', '0', '+', '#', '1', '0', '0', '=', '0']
V
<sum_2_get_next> : ['#', '#', '1', '0', '+', '#', '1', '0', '0', '=', '0']
V
<sum_3> : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0']
V
<sum_3> : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0']
V
<sum_3> : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0']
V
<write_3> : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0']
V
<write_3> : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', ' ']
V
<move_left_carry_1> : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
V
<move_left_carry_1> : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
V
<move_left_carry_1> : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
V
<move_left_carry_1> : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
V
<move_left_carry_1> : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
V
<move_left_carry_1> : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
V
<move_left_carry_1> : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
V
<move_left_carry_1_part_2> : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
V
<move_left_carry_1_part_2> : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
V
<move_left_carry_1_part_2> : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
V
<mark_start_carry_1> : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
V
<sum_2> : ['#', '#', '#', '0', '+', '#', '#', '0', '0', '=', '0', '1']
V
<sum_2> : ['#', '#', '#', '0', '+', '#', '#', '0', '0', '=', '0', '1']
V
<sum_2_get_next> : ['#', '#', '#', '0', '+', '#', '#', '0', '0', '=', '0', '1']
V
<sum_2_get_next> : ['#', '#', '#', '0', '+', '#', '#', '0', '0', '=', '0', '1']
V
<sum_2_get_next> : ['#', '#', '#', '0', '+', '#', '#', '0', '0', '=', '0', '1']
V
<sum_2> : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1']
V
<sum_2> : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1']
V
<write_2> : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1']
V
<write_2> : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1']
V
<write_2> : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', ' ']
V
<move_left_carry_1> : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
V
<move_left_carry_1> : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
V
<move_left_carry_1> : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
V
<move_left_carry_1> : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
V
<move_left_carry_1> : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
V
<move_left_carry_1> : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
V
<move_left_carry_1> : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
V
<move_left_carry_1> : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
V
<move_left_carry_1_part_2> : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
V
<move_left_carry_1_part_2> : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
V
<mark_start_carry_1> : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
V
<sum_1> : ['#', '#', '#', '#', '+', '#', '#', '#', '0', '=', '0', '1', '0']
V
<sum_1_get_next> : ['#', '#', '#', '#', '+', '#', '#', '#', '0', '=', '0', '1', '0']
V
<sum_1_get_next> : ['#', '#', '#', '#', '+', '#', '#', '#', '0', '=', '0', '1', '0']
V
<sum_1_get_next> : ['#', '#', '#', '#', '+', '#', '#', '#', '0', '=', '0', '1', '0']
V
<sum_1_get_next> : ['#', '#', '#', '#', '+', '#', '#', '#', '0', '=', '0', '1', '0']
V
<sum_1> : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0']
V
<write_1> : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0']
V
<write_1> : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0']
V
<write_1> : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0']
V
<write_1> : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', ' ']
V
<move_left_carry_0> : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
V
<move_left_carry_0> : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
V
<move_left_carry_0> : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
V
<move_left_carry_0> : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
V
<move_left_carry_0> : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
V
<move_left_carry_0> : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
V
<move_left_carry_0> : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
V
<move_left_carry_0> : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
V
<move_left_carry_0> : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
V
<move_left_carry_0_part_2> : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
V
<mark_start_carry_0> : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
####+####=0101
'accept'
I think this machine can be simplified by writing the carry directly to the tape (i.e. writing a ’0′, a ’1′ or a ’2′ to the result part of the tape, and later converting the ’2′s to ’1′ and ’0′ as appropriate).
If anyone of you manages to generate an equivalent machine with a shorter description (less states) please post it!
October 9th, 2007 at 8:03 pm
Really nice.
)
Any chance to see the code drawing the graph? (or at least the name of the library you used
Maybe you’ll be interested in this:
http://www.wolframscience.com/prizes/tm23/index.html
October 14th, 2007 at 2:26 pm
Dani,
I used an external program called dotty (http://www.graphviz.org/).
Although I think there is a wrapper for python, I did not use it, but rather wrote a function that generates the “.dot” files themselves. The format is extremely simple.
Your link seems interesting. I will have a deeper look at it when I’ll get to it.
October 26th, 2007 at 7:00 pm
The Wolfram challenge was solved 2 days ago:
http://www.wolframscience.com/prizes/tm23/solved.html