Notes

Chapter 12: The Principle of Computational Equivalence

Section 9: Implications for Mathematics and Its Foundations


Properties [of example multiway systems]

For most of the rules shown, there ultimately turn out to be quite easy characterizations of what strings can be produced.

• (a) At step t, the only new string produced is the one containing t black elements.

• (b) All strings of length n containing exactly one black cell are produced—after at most 2n-1 steps.

• (c) All strings containing even-length runs of white cells are produced.

• (d) The set of strings produced is complicated. The last length 4 string produced is , after 16 steps; the last length 6 one is , after 26 steps.

• (e) All strings that begin with a black element are produced.

• (f) All strings that end with a white element but contain at least one black element, or consist of all white elements ending with black, are produced. Strings of length n take n steps to produce.

• (g) The same strings as in (f) are produced, but now a string of length n with m black elements takes n+m-1 steps.

• (h) All strings appear in which the first run of black elements is of length 1; a string of length n with m black elements appears after n+m-1 steps.

• (i) All strings containing an odd number of black elements are produced; a string of length n with m black cells occurs at step n+m-1.

• (j) All strings that end with a black element are produced.

• (k) Above length 1, the strings produced are exactly those starting with a white element. Those of length n appear after at most 3n-3 steps.

• (l) The same strings as in (k) are produced, taking now at most 2n+1 steps.

• (m) All strings beginning with a black element are produced, after at most 3n+1 steps.

• (n) The set of strings produced is complicated, and seems to include many but not all that do not end with .

• (o) All strings that do not end in are produced.

• (p) All strings are produced, except ones in which every element after the first is white. takes 14 steps.

• (q) All strings are produced, with a string of length n with m white elements taking n + 2m steps.

• (r) All strings are ultimately produced—which is inevitable after the lemmas -> and -> appear at steps 12 and 13. (See the first rule on page 778.)


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