A construction of five-state real-time Fibonacci sequence generator

A cellular automaton (\(\mathrm {CA}\)) is a well-studied non-linear computational model of complex systems in which an infinite one-dimensional array of finite state machines (cells) updates itself in a synchronous manner according to a uniform local rule. A sequence generation problem on the \(\mathrm {CA}\) model has been studied for a long time and a lot of generation algorithms has been proposed for a variety of non-regular sequences such as \(\{2^n \,|\,n = 1, 2, 3,\ldots \}\), prime, and Fibonacci sequences, etc. In this paper, we propose a five-state real-time generator for Fibonacci sequence and give a formal proof of the correctness of the generator. The proposed five-state Fibonacci sequence generator is optimum in generation steps, and it is realized on a smallest, known at present finite state automaton in the number of states.