Complexity and Universality of Iterated Finite Automata
Jiang Zhang
Complex Systems Research Center
Academy of Mathematics and Systems Science
Chinese Academy of Sciences
No. 55 Zhong Guan Cun Dong Lu
Beijing, 100080, China
Zhangjiang@amss.ac.cn
Abstract
The iterated finite automaton (IFA) was invented by Stephen Wolfram for studying the conventional finite state automaton (FSA) by means of A New Kind of Science methodology. An IFA is a composition of an FSA and a tape with limited cells. The complexity of behaviors generated by various FSAs operating on different tapes can be visualized by two-dimensional patterns. Through enumerating all possible two-state and three-color IFAs, this paper shows that there are a variety of complex behaviors in these simple computational systems. These patterns can be divided into eight classes such as regular patterns, noisy structures, complex behaviors, and so forth. Also they show the similarity between IFAs and elementary cellular automata. Furthermore, any cellular automaton can be emulated by an IFA and vice versa. That means IFAs support universal computation.
