There are two kinds of algorithmic irreducibility: time irreducibility as in Wolfram [1], and information irreducibility as in Chaitin [2,3] and Calude [4]. In the first case, a physical system for which there are no computational shortcuts, for which the quickest way to see what the system does is just to run it. In the second case, a string of bits for which there is no theory more compact than being given the string of bits directly as is. In other words, there is no program for calculating the string of bits that is substantially smaller than the string of bits itself.
In this note we shall consider how to produce irreducible information in a toy world, a two-dimensional cellular automata. Such highly simplified model universes have a long history, going back to Zuse [5] and von Neumann [6]. They feature homogeneous spaces populated by identical finite-state automata. Time as well as space is quantized, and the state of each cell at a given time is a deterministic function of its previous state and the state of its four immediate neighbors (up, down, left, right). In such a world effects only propagate locally, and there is a "finite speed of light," i.e., maximum speed of propagation.
The canonical example of irreducible information is the infinite sequence of bits in the base-two expansion of the halting probability Ω. The halting probability is defined taking the following summation
over all the self-delimiting programs p that halt when run on a suitably defined universal Turing machine U. Here |p| denotes the size in bits of the program p. The value of Ω depends on the choice of U, but its surprising properties do not.
The numerical value of Ω is maximally unknowable in the following precise sense. You need an N-bit theory in order to be able to determine N bits of Ω [7]. Nevertheless, Ω has a kind of diophantine reality, because there is a diophantine equation with a parameter k that has finitely or infinitely many solutions depending on whether the kth bit of Ω is respectively 0 or 1 [2]. More recently, Ord and Kieu [8] have shown that there is also a diophantine equation with a parameter k that has an even or odd number of solutions depending on whether the kth bit of Ω is respectively 0 or 1.
The purpose of this note is to discuss the fact that as well as "diophantine reality," Ω also possess a kind of physical reality, because there is a cellular automata world which in the limit of infinite time contains the infinite sequence of bits bi in the binary expansion of Ω:
The conventional way of performing computation in a cellular automata is to utilize a one-dimensional array of cells and to simulate a Turing machine with an alphabet of α different symbols and a set of σ different internal states in the following manner. The one-dimensional cellular automata that simulates this α-symbol σ-state Turing machine consists of identical cells each having precisely (1+σ) × α different internal states. Each of these states consists of a pair. The first element of the pair indicates either an inactive cell or the internal state of the read-write head of the Turing machine. The second element of the pair indicates the symbol written in the corresponding cell of the two-way infinite one-dimensional tape of the Turing machine.
We think, however, that it is more interesting to follow [2] in using a simple version of LISP instead of Turing machines. This is a version of LISP in which each atom is a single character and in which S-expressions are represented as character strings. Such a simplified LISP may be imbedded in a cellular automata world. More precisely, the two-dimensional cellular automata that we have in mind is actually a LISP interpreter. Then one can calculate better and better lower bounds on Ω by using a simple LISP function given in [2] for calculating Ω as the limit of Ωn defined as follows:
As n tends to infinity, Ωn tends to Ω, and from some point on each bit of Ωn will remain correct, since Ω is irrational.
Working out all the details of the design of a cellular automata that is a LISP interpreter is an onerous but not a particularly intellectually challenging task. In a two-dimensional world, it is easy to partition the space into quadrants, one of which is a clock containing the current value of n represented as a list of n 1's, one of which contains the current value of Ωn, and one of which contains the LISP interpreter's recursive push-down stack.
As n tends to infinity, the values of individual bits of Ωn will fluctuate but eventually settle down to the correct values. In my opinion this is a cute way to give Ω, which is irreducible information, a kind of physical reality, at least to the extent to which a two-dimensional cellular automata itself has that kind of reality.