# Implementation-level description of a Turing Machine

I am new to Turing Machines!

I need to work on an implementation-level description of a Turing machine that decides the language L = an where n is a Fibonacci number.

I know Fibonacci numbers include 1 1 2 3 5 8 13 21 34 55 89 144 233 377...

So would this be as

M= "On input a^n:
Scan a^n, if a '1' is found, cross it out, and move the head
of the tape back to the left-hand end, and then go to II
(****could I make II my accept state? Or should I make two the recursive calculation I explain in C below?)

If a '0' is found, cross it out, and go to the reject state
(can I make this three?)
II. Accept
III. Reject


I want to incorporate the recursion aspect of this in the implementation. Because if I were in C, and n is not a 0 or 1, it is a fibonacci number if you do a sort of fib(n) where inside it 'return fib(n-1) + fib(n-2)'.

Thoughts? Thank you.

One approach is using Fibonacci words (each word is the concatenation of the preceding two words): \begin{align*} &0 \\ &01 \\ &010 \\ &01001 \\ &01001010 \end{align*} You can generate them according to the following scheme: \begin{align*} &\color{blue}0\color{red}1 \to \color{blue}0\color{red}1\color{green}0 \to \color{blue}{01}\color{green}0 \to \\ &\color{blue}{01}\color{red}0 \to \color{blue}{01}\color{red}0\color{green}{01} \to \color{blue}{010}\color{green}{01} \to \\ &\color{blue}{010}\color{red}{01} \to \color{blue}{010}\color{red}{01}\color{green}{010} \to \color{blue}{01001}\color{green}{010} \to \\ &\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.
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.