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!
These are two nice and easy gambling related riddles.
and Real Madrid C.F. 
will be playing 7 games against each other this season. I give you $1,000 and ask you to double it in case Barça wins overall (i.e. if they win at least 4 of the 7 games). You are allowed to lose all of it otherwise.
There are 3 types of lizards: yellow, green and blue.
There are 10 cells in a line. A transparent rabbit is in one of them. You have a shotgun, and obviously you want to shoot the rabbit.
Two aunts are living each in her own (0-dimensional) house. There are two non-intersecting (1-dimensional) roads between the houses.
For inspirational music, 
This riddle is a very cool extension of a well known (and easy) riddle, involving people with hats waiting in a line.
).
There are 100 red dots and 100 blue dots on the plane (a lot of planar riddles lately). The dots are arranged such that no three are on the same line.
A very easy riddle. Four frogs are sitting on the corners of the unit square (i.e. they have coordinates (0,0), (0,1), (1,1) and (1,0) ). Each turn, a frog can jump over any other frog, thereby transferring itself to the symmetrical point on the other side of the static frog. For example, if the frog at (0,0) jumps over the frog at (1,1) it will land on (2,2).
).
This is a cute puzzle. Consider an infinite checkerboard divided in two with an infinite line lying along the x-axis, as depicted below:
In this post I will give a basic example of the necessity (or uselessness – its up to you to choose – pun intended) of the axiom of choice. I will also present a less known proof of the Cantor–Bernstein–Schroeder theorem.
I recently watched 
How can you cut a circular cake to eight even pieces with 3 cuts? What is the maximum number of pieces possible with 4 cuts?
You have a rare and fatal disease. The only cure for your disease is taking one 
You have a cup of coffee and a cup of milk, both containing the same (unspecified) amount of liquid. You take one spoon full of milk and put it in the coffee. You mix well. You then return a spoon full of the mixture to the cup of milk. Which is more: milk in coffee or coffee in milk?
You are shipwrecked on the Virgin Islands (since 
There are 100 seats in an airplane.
There are 100 coins on the table. 90 of the coins have their Heads face up, the other 10 have their Tails face up. Your task is to split the coins into two groups, such that both groups contain the same number of coins with their Heads face up. You are even allowed to flip the coins…
).
I am taking a course about 
Yesterday, Zohar Gilboa, with whom I take a PDE course, asked me the following riddle. I must admit it is probably the riddle I like the least on my site thus far. It is very easy though, and as Zohar told me he really liked it himself, I decided to publish it anyways.
This one is a riddle of my own invention. I am really proud of it as it sounds impossible at first, but it can be resolved in a very satisfying fashion. I must admit that had I heard about it from someone else I would not have gone through the trouble of trying to solve it, as it sounds like a ”cheap-trick” riddle. I can only ask you to trust me that it is indeed a purely mathematical riddle. Although it did provoke several harsh disputes with some very smart people (Matan, Eyal, how are you guys?), I was able to finally convince them of the mathematical validity of my solution.
