Implementation-level description of a Turing Machine
One approach is using Fibonacci words (each word is the concatenation of the preceding two words):
$$
\begin{align*}
&amp;0 \\
&amp;01 \\
&amp;010 \\
&amp;01001 \\
&amp;01001010
\end{align*}
$$
You can generate them according to the following scheme:
$$
\begin{align*}
&amp;\color{blue}0\color{red}1 \to \color{blue}0\color{red}1\color{green}0 \to
\color{blue}{01}\color{green}0 \to \\
&amp;\color{blue}{01}\color{red}0 \to \color{blue}{01}\color{red}0\color{green}{01} \to \color{blue}{010}\color{green}{01} \to \\
&amp;\color{blue}{010}\color{red}{01} \to \color{blue}{010}\color{red}{01}\color{green}{010} \to \color{blue}{01001}\color{green}{010} \to \\
&amp;\color{blue}{01001}\color{red}{010} \to \cdots
\end{align*}
$$
I hope the algorithm is clear. The basic operations are copying of words and changing colors. 

Why is this helpful? The lengths of the Fibonacci words are exactly the Fibonacci numbers. If you can compare lengths of words, then by generating the sequence of Fibonacci words, at some point you will either reach or exceed the input, and using that information will be able to decide your language.

While I explained how to generate the Fibonacci words, you can actually just generate the words $a^{F_n}$ directly, which is slightly easier. You can even do that on top of your input for a really slick approach.