:  addBinary program
:  Ruleset for Turing Machine
:
:  David Klick
:  May 2008
:
:  This program adds two binary numbers together.
:  Sample tape: 1011+0101
:

init0:01:init1::L
init1: :add=::R
add=:01+:add=::R
add=: :bk:=:L

bk:_:bk::L
bk:0:s0:_:L
bk:1:s1:_:L
bk:+:sd::L

bkc:_:bkc::L
bkc:0:s1:_:L
bkc:1:s2:_:L
bkc:+:sdc::L

s0:01:s0::L
s0:+:f0::L
s1:01:s1::L
s1:+:f1::L
s2:01:s2::L
s2:+:f2::L

sd:0:is0:_:R
sd:1:is1:_:R
sd:_:sd::L
sd: :isdone::R

sdc:0:is1:_:R
sdc:1:is2:_:R
sdc:_:sdc::L
sdc: :isdonec::R

f0:0:is0:_:R
f0:1:is1:_:R
f0:_:f0::L
f0: :is0::R
f1:0:is1:_:R
f1:1:is2:_:R
f1:_:f1::L
f1: :is1::R
f2:0:is2:_:R
f2:1:is3:_:R
f2:_:f2::L
f2: :is2::R

isdone:01+=_:isdone::R
isdone: :halt::S
isdonec:01+_:isdonec::R
isdonec:=:insert1::R
insert1:0:insert0:1:R
insert1:1:insert1:1:R
insert1: :halt:1:R
insert0:0:insert0:0:R
insert0:1:insert1:0:R
insert0: :halt:0:R

is0:01+_:is0::R
is0:=:ins0::R
is1:01+_:is1::R
is1:=:ins1::R
is2:01+_:is2::R
is2:=:ins0c::R
is3:01+_:is3::R
is3:=:ins1c::R

bkup:01:bkup::L
bkup:=:bk::L
bkupc:01:bkupc::L
bkupc:=:bkc::L

ins0:0:ins0:0:R
ins0:1:ins1:0:R
ins0: :bkup:0:L
ins1:0:ins0:1:R
ins1:1:ins1:1:R
ins1: :bkup:1:L

ins0c:0:ins0c:0:R
ins0c:1:ins1c:0:R
ins0c: :bkupc:0:L
ins1c:0:ins0c:1:R
ins1c:1:ins1c:1:R
ins1c: :bkupc:1:L