# Math Help - Fibonacci Sequence on Turing Machine

1. ## Fibonacci Sequence on Turing Machine

Hey, my Discrete Math teacher wants me to simulate Fibonacci's sequence on a Turing Machine using Visual Turing program. I didn't sleep last night trying to solve this thing. Need some help from you guys .

2. Originally Posted by thegodthatfailed
Hey, my Discrete Math teacher wants me to simulate Fibonacci's sequence on a Turing Machine using Visual Turing program. I didn't sleep last night trying to solve this thing. Need some help from you guys .
Well start by deciding exactly what you want the TM to do.

1. Start on an otherwise blank tape marked with $n$ $1$'s (I am assuming the alphabet the symbols may be chossen from is $\{1\}$) with the reading head positioned over the rightmost non-blank cell. Finish with an otherwise blank tape with the reading head over the right most $1$ of a block $F_n$ $1$'s

2. Start over on an otherwise blank tape marked with $F_n$ $1$'s seperated by one blank from a block of $F_{n-1}$ $1$'s, end with a tape otherwise blank with $F_{n+1}$ and $F_n$ $1$'s seperated by a blank.

...

CB