# Thread: 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 $\displaystyle n$ $\displaystyle 1$'s (I am assuming the alphabet the symbols may be chossen from is $\displaystyle \{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 $\displaystyle 1$ of a block $\displaystyle F_n$ $\displaystyle 1$'s

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

...

CB

### fibonacci sequance turing

Click on a term to search for related topics.