Notes

Chapter 12: The Principle of Computational Equivalence

Section 8: Undecidability and Intractability


Rule 30 inversion

The total numbers of sequences for t from 1 to 15 not yielding stripes of heights 1 and 2 are respectively

{1, 2, 2, 3, 3, 6, 6, 10, 16, 31, 52, 99, 165, 260} {2, 5, 8, 14, 23, 40, 66, 111, 182, 316, 540, 921, 1530, 2543, 4122}

The sideways evolution of rule 30 discussed on page 601 implies that if one fills cells from the left rather than the right then some sequence of length t+1 will always yield any given stripe of height t.

If the evolution of rule 30 can be set up as on page 704 to emulate any Boolean function then the problem considered here is immediately equivalent to satisfiability.


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