Add two binary numbers on a single tape Turing machine (http://morphett.info/turing/turing.html)

turing-1tape-add.txt

; Turing 1-tape addition calculator
; The answer is first written in reverse binary
; Example input: 11011000+00011111=

; Find equals sign
0 * * r 0
0 = = r init-carry

; Write initial carry bit
init-carry _ 0 l init-carry
init-carry = = l add

; Go to least significant rhs digit
add x x l add
add 0 x * add0
add 1 x * add1

; Default rhs bit to 0
add + + r add0

; Go to + sign
add0 * * l add0
add1 * * l add1
add0 + + l add0+
add1 + + l add1+

; Go to least significant lhs digit
add0+ x x l add0+
add1+ x x l add1+
add0+ 0 x * add00
add0+ 1 x * add01
add1+ 0 x * add10
add1+ 1 x * add11

; Default lhs to 0
add0+ _ _ r add00
add1+ _ _ r add10

; Find carry bit (last character)
add00 * * r add00
add01 * * r add01
add10 * * r add10
add11 * * r add11

add00 _ * l add00c
add01 _ * l add01c
add10 _ * l add10c
add11 _ * l add11c

; Write result and compute carry bit
add00c 0 0 r carry0
add00c 1 1 r carry0
add01c 0 1 r carry0
add01c 1 0 r carry1
add10c 0 1 r carry0
add10c 1 0 r carry1
add11c 0 0 r carry1
add11c 1 1 r carry1

; Write carry bit
carry0 _ 0 * return
carry1 _ 1 * return

; Return to equals sign
return * * l return
return = = l check

; Check if there is any input left
check * * l check
check 0 0 * check-true
check 1 1 * check-true
check _ _ r check-false

; Return to equals sign if there is input left
check-true * * r check-true
check-true = = l add

; Go to end and start reversing number
check-false * * r check-false
check-false _ = l reverse

; Find first digit before this =
reverse * * l reverse
reverse 0 x r bit0
reverse 1 x r bit1

; Terminate if reverse finds =
reverse = = * halt-done

; Go to the end and write bit
bit0 * * r bit0
bit1 * * r bit1
bit0 _ 0 * return2
bit1 _ 1 * return2

; Return to equals sign
return2 * * l return2
return2 = = l reverse