Recognition Algorithms for Fibonacci Numbers

Document Type


Publication Date



The Fibonacci Association


FORTRAN, BASIC, or ALGOL program to generate Fibonacci numbers is not unfamiliar to many mathematicians. A Turing machine or a Markov algorithm to recognize Fibonacci numbers is, however, considerably more abstruse.

A Turing machine, an abstract mathematical system which can simulate many of the operations of computers, is named after A.M. Turing who first described such a machine in [2]„ It consists of three main parts: (1) a finite set of states or modes; (2) a tape of infinite length with tape reader; (3) a set of instructions or rules* The tape reader can read only one character at a time, and, given the machine state and tape symbol, each instruction gives us information consisting of three parts; (1) the character to be written on the tape, (2) the direction in which the tape reader is to move; (3) the new state the machine is to be in.