Notes

Chapter 12: The Principle of Computational Equivalence

Section 4: The Validity of the Principle


Continuum and cardinality

Some notion of a distinction between continuous and discrete systems has existed since antiquity. But in the 1870s the distinction became more precise with Georg Cantor's characterization of the total numbers of possible objects of various types in terms of different orders of infinity (see page 1162). The total number of possible integers corresponds to the smallest level of infinity, usually denoted Aleph0. The total number of possible lists of integers of given finite length—and thus the number of possible rational numbers—turns out also to be Aleph0. The reason is that it is always possible to encode any finite list of integers as a single integer, as discussed on page 1120. (A way to do this for pairs of non-negative integers is to use σ[{x_, y_}] := (x + y)(x + y + 1)/2 + x.) But for real numbers the story is different. Any real number x can be represented as a set of integers using for example

Rest[FoldList[Plus, 1, ContinuedFraction[x]]]

but except when x is rational this list is not finite. Since the number of possible subsets of a set with k elements is 2^k, the number of possible real numbers is 2^Aleph0. And using Cantor's diagonal argument (see note below) one can then show that this must be larger than Aleph0. (The claim that there are no sets intermediate in size between Aleph0 and 2^Aleph0 is the so-called continuum hypothesis, which is known to be independent of the standard axioms of set theory, as discussed on page 1155.) Much as for integers, finite lists of real numbers can be encoded as single real numbers—using for example roughly FromDigits[Flatten[Transpose[RealDigits[list]]]]—so that the number of such lists is 2^Aleph0. (Space-filling curves yield a more continuous version of such an encoding.) But unlike for integers the same turns out to be true even for infinite lists of real numbers. (The function σ above can for example be used to specify the order in which to sample elements in RealDigits[list]). The total number of possible functions of real numbers is 2^(2^Aleph0; the number of continuous such functions (which can always be represented by a list of coefficients for a series) is however only 2^Aleph0.

In systems like cellular automata, finite arrangements of black cells on a background of white cells can readily be specified by single integers, so the number of them is Aleph0. But infinite configurations of cells are like digit sequences of real numbers (as discussed on page 869 they correspond more precisely to elements in a Cantor set), so the number of them is 2^Aleph0. Continuous cellular automata (see page 155) also have 2^Aleph0 possible states.


From Stephen Wolfram: A New Kind of Science [citation]