A two-tape deterministic Turing machine that recognizes an exponential string
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| )$.