Can unary be used in Turing Machine?

Question

Given a number in unary (0 = 1, 1 = 11, 2 = 111, 3 = 1111, ...), leave one blank symbol after it, and write the binary representation of the same number (0 = 0, 1 = 1, 2 = 10, 3 = 11, 4 = 100, ...). It is acceptable (not required) to write the number in a reverse order. When done, the TM should switch to the accepting state. No need to verify input, assume that input is 100% one unary number, and there is nothing else written on the tape.

Answer 1

Another approach is marking every other 1 (as 0) in the unary input and append in the second section a 1 when the last occurrence of 1 was marked by this process, otherwise append a 0. When there are no more 1 in the input section, restore them back to 1 and halt (accept).

This will place the big-endian binary representation in the output section (so in "reverse"). NB: It would not require much more effort to produce the little-endian representation.

Here is a transition table for that algorithm:

state	read	write	move head	next state
start	1	0	right	odd
start	0		right	start
start	_		left	clean
odd	0		right	odd
odd	1		right	even
odd	_		right	append1
even	0		right	even
even	1	0	right	odd
even	_		right	append0
append0	0 or 1		right	append0
append0	_	0	left	center
append1	0 or 1		right	append1
append1	_	1	left	center
center	0 or 1		left	center
center	_		left	left
left	0 or 1		left	left
left	_		right	start
clean	0	1	left	clean
clean	_		right	halt

And a runnable implementation:

createTuring({
    transitions: [
        { state: "start",   read: "1",  write: "0", move: "R", nextState: "odd"     },
        { state: "start",   read: "0",              move: "R", nextState: "start"   },
        { state: "start",   read: "_",              move: "L", nextState: "clean"   },
        { state: "odd",     read: "0",              move: "R", nextState: "odd"     },
        { state: "odd",     read: "1",              move: "R", nextState: "even"    },
        { state: "odd",     read: "_",              move: "R", nextState: "append1" },
        { state: "even",    read: "0",              move: "R", nextState: "even"    },
        { state: "even",    read: "1",  write: "0", move: "R", nextState: "odd"     },
        { state: "even",    read: "_",              move: "R", nextState: "append0" },
        { state: "append0", read: "01",             move: "R", nextState: "append0" },
        { state: "append0", read: "_",  write: "0", move: "L", nextState: "center"  },
        { state: "append1", read: "01",             move: "R", nextState: "append1" },
        { state: "append1", read: "_",  write: "1", move: "L", nextState: "center"  },
        { state: "center",  read: "01",             move: "L", nextState: "center"  },
        { state: "center",  read: "_",              move: "L", nextState: "left"    },
        { state: "left",    read: "01",             move: "L", nextState: "left"    },
        { state: "left",    read: "_",              move: "R", nextState: "start"   },
        { state: "clean",   read: "0",  write: "1", move: "L", nextState: "clean"   },
        { state: "clean",   read: "_",              move: "R", nextState: "halt"    },
    ],
    initState: "start",
    tape: "11111111111",
});

<script src="https://trincot.github.io/turing.js"></script>

This has a time complexity of O(𝑛log𝑛).

Answer 2

Here is a solution based on Welbog's hint.

The TM will begin by writing a 0 one blank space after the end of the 1s. We know there will be at least a single 1 on the tape. Then, we can add one to our binary representation for each 1 we see to the left of the first blank. We may as well remember which unary 1s we've already processed by changing them to 0s. If we want to put the tape back like it was when we're done, we can write 1s back over the 0s to the left of the binary representation.

Q    T    Q'    T'    d
-----------------------
q0   1    q0    1     R    // scan right to first blank space
q0   #    q1    #     R    // after unary. then, write a 0
q1   #    q2    0     L    // to start the binary.

q2   #    q3    #     L    // scan left past any binary data
q2   0    q2    0     L    // to get to the blank separating
q2   1    q2    1     L    // unary and binary

q3   #    hA    #     R    // scan left for another unary
q3   0    q3    0     L    // digit, ignoring ones that have
q3   1    q4    0     R    // been processed. if done, halt.

q4   #    q5    #     R    // scan right to the blank separating
q4   0    q4    0     R    // unary and binary

q5   #    q2    1     L    // add one to the binary representation
q5   0    q2    1     L    // by toggling bits until you toggle a
q5   1    q5    0     R    // zero to a one, completing the addition

Example:

#111####  =>  #111####  =>  #111####  =>  #111####  => (next line)
 ^q0            ^q0            ^q0            ^q0

#111####  =>  #111#0##  =>  #111#0##  =>  #110#0##  => (next line)
     ^q1          ^q2          ^q3            ^q4

#110#0##  =>  #110#1##  =>  #110#1##  =>  #110#1##  => (next line)
     ^q5          ^q2          ^q3          ^q3

#100#1##  =>  #100#1##  =>  #100#1##  =>  #100#0##  => (next line)
   ^q4            ^q4            ^q5            ^q5

#100#01#  =>  #100#01#  =>  #100#01#  =>  #100#01#  => (next line)
     ^q2          ^q2          ^q3          ^q3

#100#01#  =>  #000#01#  =>  #000#01#  =>  #000#01#  => (next line)
 ^q3            ^q4            ^q4            ^q4

#000#01#  =>  #000#11#  =>  #000#11#  =>  #000#11#  => (next line)
     ^q5          ^q2          ^q3          ^q3

#000#11#  =>  #000#11#  =>  #000#11#
 ^q3          ^q3            ^hA