Turing machine that computes exponential function

Question

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?

Answer 1

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$.

Answer 2

The basic idea is that the machine keeps doubling its intermediate result until it has done that $n$ times (i.e until you run out of the lines that represent the input $n$).

The issue of course that you represent the number $n$ with $n+1$ lines.

This is why they immediately remove one line from the input before doing anything, so you have $n$ lines instead of $n+1$, ensuring that you go into the doubling routine $n$ times rather than $n+1$.

Also, whenever you double, you should first remove one of the lines of the intermediate result, then do the 'doubling' routine, and finally add a line back to the intermediate result.

Alternatively, you can check if you are out of lines from the input ... if not, then don't bother adding the line back to it, for you immediately would have to remove it again. So, with this method, you end up just adding adding the normalization line at the very end.

Now, it is not quite clear from your description how that method handles the extra line, but the basic idea is still to double things $n$ times.