; Unary-to-Binary TM (with embedded Binary Add1 subroutine)

;-----------------------------------------------------------------
; A Turing machine for converting unary numbers to binary numbers
; by repeatedly calling the Binary Add1 machine as a "subroutine"
;
; INPUT: a block of 1's representing a number written in unary
; OUTPUT: a block of 0's and 1's representing the number in binary
;-----------------------------------------------------------------

s1 1 1 L s1    ; Write 0 to the left of the unary string, with an
s1 _ _ L s2    ; intervening space, then move back to the beginning
s2 _ 0 R s3    ; of the unary string and switch to state s4.
s3 _ _ R s4

s4 1 x R s4    ; Replace all unary 1's by x's and move to the
s4 _ _ L s5    ; rightmost x, then switch to state s5.

s5 x _ L s6    ; Erase the rightmost x.

s6 x x L s6    ; Scan leftward over the x's, and then continue
s6 _ _ L s7    ; scanning left to the beginning of the binary
s7 0 0 L s7    ; string of 0's and 1's, stopping on the leftmost
s7 1 1 L s7    ; symbol. Then switch to state b1 to add 1 to
s7 _ _ R b1    ; the binary string.

b1 0 0 R b1    ; Binary Add1 subroutine
b1 1 1 R b1
b1 _ _ L b2
b2 0 1 * b3
b2 1 0 L b2
b2 _ 1 * b3
b3 0 0 L b3
b3 1 1 L b3
b3 _ _ R s8    ; After adding 1, switch to state s8.

s8 0 0 R s8    ; Scan rightward over the binary string of 0's and
s8 1 1 R s8    ; 1's, and then continue scanning rightward to find
s8 _ _ R s9    ; the end of the string of x's.
s9 x x R s9
s9 _ _ L s5    ; Go back to state s5 to continue the loop...

s5 _ _ * halt  ; Halt when no more x's are found in state s5.