#
# A simple 2-tape DTM that performs binary addition.
#
# The two integers to be added are placed on tapes 1 and 2,
# respectively. The result is placed on the first tape.
# 
# (w) 2006, Michal Januszewski <spock@gentoo.org>

tapes = 2
alphabet = { 0, 1 }
states = { end, add0, add1, done }
istate = end
fstates = { done }

tape_0 = 00110
tape_1 = 1

# Transition function
# state	 char0	char1	->	state	char0	move0	char1	move1
# The 'i' in chari/movei is a an index identifying the tape.

tf =
# Searching for the least significant digit in both numbers
end		1	1	->	end		1	R	1	R
end		1	0	->	end		1	R	0	R
end		0	0	->	end		0	R	0	R
end		0	1	->	end		0	R	1	R
end		1	b	->	end		1	R	b	S
end		0	b	->	end		0	R	b	S
end		b	1	->	end		b	S	1	R
end		b	0	->	end		b	S	0	R
end		b	b	->	add0	b	L	b	L

# Addition with carry = 0
add0	0	0	->	add0	0	L	b	L
add0	1	0	->	add0	1	L	b	L
add0	0	1	->	add0	1	L	b	L
add0	1	1	->	add1	0	L	b	L
add0	b	0	->	add0	0	L	b	L
add0	0	b	->	add0	0	L	b	S
add0	1	b	->	add0	1	L	b	S
add0	b	1	->	add0	1	L	b	L
add0	b	b	->	done	b	S	b	S

# Addition with carry = 1
add1	0	0	->	add0	1	L	b	L
add1	1	0	->	add1	0	L	b	L
add1	0	1	->	add1	0	L	b	L
add1	1	1	->	add1	1	L	b	L
add1	b	1	->	add1	0	L	b	L
add1	1	b	->	add1	0	L	b	S
add1	0	b	->	add0	1	L	b	S
add1	b	0	->	add0	1	L	b	L
add1	b	b	->	done	1	L	b	S