A two-tape deterministic Turing machine that recognizes an exponential string

How can I describe a Turing Machine recognizing the language $P=\{a^{2^n} | n \geq 0 \}$?

This Turing Machine is deterministic and uses two tapes, both bidirectional and R / W (read & write)

The computation should be done in linear time.

I've read Counters in Turing machines but it doesn't address my question. It can help but it doesn't answer my question.
Turing Machines with $n$-tapes have the same computability that Turing Machines with one tape, but different behavior. Here I'm asking about the behavior of a two-tape TM.

My approach:

I think I may use the first tape as input tape and copy every character in the second tape. But I don't know how to keep track the exponential behavior.

To expand fade2black's answer; this is a simple proof by induction that the following TM

State    Symbol    Write  Move   Newstate
start    0         1      L      tolsb
start    1         0      R      carry

tolsb    _         _      R      start
tolsb    *         *      L      tolsb

carry    0         1      L      tolsb
carry    1         0      R      carry

performs a binary count from $0^n$ to $1^n$ in less than $2^{n} + n^3$ steps.
Initially the head is placed on the LSB (which, we assume, is on the left part of the input string).

You can view a simulation of the Turing machine here.

We prove by induction that starting on the leftmost $0$, it counts up to $1^n$ and, at the end, the head is still placed on the LSB.

• case $n = 1$:

Immediate

_ 0    start
   ^ 
 _ 1    step 1
 ^
 _ 1    step 2
   ^

• case $n$: suppose that it holds for $n-1$; i.e. it can count up from $0^{n-1}$ to $1^{n-1}$ in less than $2^{n-1} + (n-1)^3$ steps;

Then after less than $2^{n-1} + (n-1)^3$ steps the head is on LSB:

1 2 3 ...   n 
 _ 1 1 1 ... 1 0 
   ^

It will convert all $1$s to $0$ and propagate the carry to the MSB and convert the MSB to $1$ in $n$ steps:

1 2 3 ...   n 
 _ 0 0 0 ... 0 1 
             ^

Then it will go back to the LSB in $n$ steps

1 2 3 ...   n 
 _ 0 0 0 ... 0 1 
   ^

Then it will count up to $1^n$ using less than $2^{n-1} + (n-1)^3$ steps.

1 2 3 ...   n 
 _ 1 1 1 ... 1 1 
   ^

The total number of steps is less than:

$$2^{n-1} + 2^{n-1} + 2(n-1)^3 + 2n \leq 2^n + n^3$$

So if we have as input $w = a^{2^n}$; we can perform a binary count (on the second tape) in linear time $O( |w| )$.

StackExchange Computer Science Q#81878, answer score: 3