Program the Turing Machine simulator to recognize the language F of

Fibonacci numbers. That is$,$ if the length of the input is a Fibonacci number, accept; if

the length of the input is not a Fibonacci number, reject.

Examples $($We take the sequence to be $(0,1,1,2,3,5,8,13,...)$:

$\backslash$epsi in F

$0$ in F

$00$ in F

$000$ in F

$0000/$ in F

$00000$ in F

$000000/$ in F

$0000000000000000000000000000000000$ in F

$00000000000000000000000000000000000/$ in F

This has a lovely implementation with a $3-$tape Turing Machine.