Recognition Algorithms for Fibonacci Numbers
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 „ 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.
Smolarski, D. C., & Klosinski, L. F. (1981). Recognition Algorithms for Fibonacci Numbers. The Fibonacci Quarterly, 19(1), 57–61.