I want to construct a 2-tape TM, that converts a binary number into unary and takes $O(n)$ time.
Let $n \in \mathbb N$ be the number I want to convert. My idea was that I just subract 1 from bin(n) until bin(n) = 0 and each time it subracted one, I add one '1' to my unary number on the 2nd tape. But I don't know if this is the right way to go and if it indeed only takes $O(n)$
On
I hope it can help you
the $2$-state TM below is a candidate for the simplest TM that converts integers from binary notation to unary . The upper tape initially contains the input, a positive integer with most significant bit $1$. it is also used as a counter to be decremented past $0$ down to $\#11...1\#$, a number that can be interpreted as $-1$.at each decrement ,and additional $'1'$ is written on the output tape. the counter is decremented by changing the tail $100..0$ to $011..1$.
conversion of integers from binary notation to unary - diagram :
Example:
input: $\,\,\,\#100\underline{1}\#$ $\to$ $... \to$ $\#100\underline{0}\#$ $\to$ $... \to$ $\#011\underline{1}\#$ $\to$ $... \to$ $\underline{\#} 1 1 1 1 \#$
output: $\#\#\#\#\underline{\#}\#$ $\to$ $... \to$ $\#\#\#\underline{\#} 1 \#$ $\to$ $... \to$ $\#\#\underline{\#}1 1 \#$ $\to$ $... \to$ $ \underline{\#}1 1 1 1 1 1 1 1 1 \#$
If implemented properly, every subtraction will cost a number of steps proportional to the number of trailing zeroes.
Roughly, you will have $\frac n2$ numbers requiring no borrow (the odd ones); $\frac n4$ with a single borrow (doubles of an odd); $\frac n8$ with two borrows...
As the summation $\sum_{k=0}^\infty\frac k{2^k}=2$, you are on the safe $O(n)$ side.