p111

Edge of chaos and computational power

The guess that the systems at the edge of chaos have the most power full computational capability is, generally, incorrect for cellular automata. However, M. Cook proved that a cellular automaton that is neither chaotic nor periodic can be universal computers. This fact itself is not so surprising as can be guessed from, e.g., the following work, but his method of proof is interesting, according to the experts of the field (cf. http://en.wikipedia.org/wiki/Rule_110 cellular automaton). A. Dhar, P. Lakdawala, G. Mandal, and S. R. Wadia, “Role of initial conditions in the classification of the rule space of cellular automata dynamics,” Phys. Rev. E  51 , 3032-3037 (1995) constructed various cellular automata that can realize universal Turing machines (UT), and then studied their dynamical behaviors. They showed, for example, chaotic cellular automata can realize UT. This is not surprising, because restricting initial conditions appropriate, ``anything is possible’’ for a chaotic system.

Logical depth (and significance of 16-ary expression of pi)

Bennet introduced the concept of `logical depth’ [C. Bennett, “Logical depth and physical complexity,” in The Universal Turing Machine, a half century survey edited by R. Herken (Oxford UP, 1988) p227-257] to measure the complexity of a system. Informally, a system is logically deep, if it requires disproporitonately long computation to produce from its program relative to the program length. Bennet surmised that such a system should be complex. Thus, non-random sequences (in the Kolmogorov sense) can be classified into logically deep and not so deep sequences. Intuitively, a sequence that is not random algorithmically, but is statistically random is regarded complex. The conclusion looks similar to the basic idea of the edge of chaos, but logical depth pays attention not only to the patterns in the sequence but also to the generating process.

 An interesting question is whether `logical depth’ is invariant under well-defined transformations of sequences (e.g., an $n$-ary sequence to an $m$-ary sequence). It is known, however, that there is no general algorithm that can transform $n$-ary numbers to $m$-ary numbers without depending on the number of digits. Thus this suggests that a shallow 16-ary sequence could be a deep binary sequence. Notice that Kolmogorov’s randomness does not have such a problem. Thus, we realize the fundamental importance of the topic of 16-ary representation of pi in Section 2.8 footnote 141.