SOME HISTORICAL NOTES From: Stephen Wolfram, A New Kind of Science Notes for Chapter 12: The Principle of Computational Equivalence Section: The Validity of the Principle Page 1127 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 1169). The total number of possible integers corresponds to the smallest level of infinity, usually denoted . 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 . The reason is that it is always possible to encode any finite list of integers as a single integer, as discussed on page 1126. (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^. And using Cantor’s diagonal argument (see note below) one can then show that this must be larger than . (The claim that there are no sets intermediate in size between and 2^ is the so-called continuum hypothesis, which is known to be independent of the standard axioms of set theory, as discussed on page 1161.) 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^. (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^); the number of continuous such functions (which can always be represented by a list of coefficients for a series) is however only 2^. 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 . 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^. Continuous cellular automata (see page 155) also have 2^ possible states. Stephen Wolfram, A New Kind of Science (Wolfram Media, 2002), page 1127. © 2002, Stephen Wolfram, LLC