I want to construct a composite turing machine that computes the function $f:\mathbb{N}_0\rightarrow \mathbb{N}$, $f(n)=2^n$.
At a suggested solution it is used a normalized turing machine. The machine copies the input, deletes the normalization line and puts two lines on the right of the copied input. These represent the intermedian result $2^0=1$, that has to be doubled for each remained line in the input. Now a loop is applied, that deletes a line of the copied input, copied the result till now and (using a non-normalized addition machine $T_+$ that deletes its arguments) and adds the copy to the recent result (in that way the intermediate result is doubled). The loop stops if there is no line at the copied input, and then the final result is translated to the right position.
$$$$
The normalized representation of the natural number $n$ uses $n+1$ lines, i.e., the number $3$ is represented by ||||.
I haven't really understtod why the above describes $2^n$. Could you explain it to me?
Best Answer
What does $2^n$ represent? It's 1, multiplied by 2, multiplied by 2, multiplied by 2, ..., multiplied by 2 - where there are exactly $n$ copies of "multiplied by 2" in that list.
So if I start with the pair $(n, |)$ (i.e. I have $n$ tally marks on one side and a single tally on the other), and at each step I remove one mark from the left and double the ones on the right, at the end of the process I will have doubled the tally on the right $n$ times, which is exactly what I needed to get to $2^n$.