Implementation-level description of a Turing Machine

Question

I am new to Turing Machines!

I need to work on an implementation-level description of a Turing machine that decides the language L = aⁿ 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.

Answer 1

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.

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.