Definition and Identification of Information Storage and Processing Capabilities as Possible Markers for Turing Universality in Cellular Automata
Yanbo Zhang
Physical Department
University of Science and Technology of China
Hefei, Anhui, P. R. China
Abstract
To identify potential universal cellular automata (CAs), a method is developed to measure the information processing capacity of elementary cellular automata (ECAs). Two features of CAs are considered: ability to store information and ability to process information. Local collections of cells are defined as particles of CAs and the information contained by particles is examined. By using this method, information channels and intersections of channels can be shown. By observing these two features, potential universal CAs are classified into a certain class, and all ECAs can be classified into four groups, which correspond to Wolfram's four classes: 1, homogeneous; 2, regular; 3, chaotic and 4, complex. This result shows that using the abilities of storing and processing information to characterize complex systems is effective and succinct. It is found that these abilities are capable of quantifying the complexity of systems.
Keywords: cellular automata; Turing universality; cellular automata classification
