; binary-to-unary.tm
;
; Convert a binary number to unary notation
; write a string of consecutive 1's whose number is determined
; by the input binary number.
; To be copied and pasted onto the online simulator
; http://morphett.info/turing/turing.html
; The machine starts with a binary number, and the current position on the least significant digit, e.g. "10010"
; During execution, the machine repeatedly decreases the binary number and appends a '1' to the unary string.
; At the end, the output will be a sequence of ones (in the example, 18).
; The initial input must be formulated, for instance, as "1001*0", where the asterisk
; defines the initial position of the machine. The initial state ("advanced settings" is "decrease").
; ------------------------------------------
; start by decreasing the binary number
decrease 0 1 l decrease ; while finding 0's, change to one and borrow from left
decrease 1 0 r move_right ; as soon as a 1 is found, the decrease is done
decrease _ _ r erase_binary ; if no 1 is found, then underflow (the number was 0), we are almost done
; after decreasing, move to the unary part
move_right 0 0 r move_right ; still on the binary number, keep moving
move_right 1 1 r move_right ; still on the binary number, keep moving
move_right _ _ r append_one ; we are out of the binary number, proceed with appending 1 to the unary number
; go to the right of the unary number and add a "1"
append_one 1 1 r append_one ; Still on the unary number, keep moving
append_one _ 1 l back_to_binary ; Out of the unary number, write a "1" and go back to the binary number
; Move left until the unary number ends
back_to_binary 1 1 l back_to_binary ; still inside, keep moving
back_to_binary _ _ l decrease ; on the left of the unary number: by moving one more step to the left, we get to the binary number
; Cleanup phase when the binary number underflows
erase_binary 1 _ r erase_binary ; while on a borrowed 1, replace with blank and keep moving right
erase_binary _ _ r move_to_end_of_unary ; if no more binary digits, move to the beginning of the unary number
; move to the rightmost unary digit
move_to_end_of_unary 1 1 r move_to_end_of_unary ; while in the number, keep moving
move_to_end_of_unary _ _ l halt ; if outside, step back and halt.