Design Turing machine for 2^n

Question

Design a Turing machine to compute the function

p(n)=2^n

I know how to write a code for the function 2n, but I am stuck with writing n copies of 2. Can anyone help me out? Thank you very much.

Answer 1

If you can write a Turing machine that doubles its input, then you can pretty easily adapt it to the following pseudocode (which assumes the input is non-negative, and that you have at least one more symbol available than what you use to write the input and output numbers, for instance a blank):

1. Write down $1$ to the left of the input, with some marker symbol between them. This will become the output.

2. Repeat the following:

   • If the input is zero, terminate

   • Decrease the input by $1$

   • Double the output