History [of register machines] Register machines (also known as counter machines and program machines) are a fairly obvious idealization of practical computers, and have been invented in slightly different forms several times.

But experiments—the most direct of which are based on looking for quantization in the measured decay times of very short-lived particles—have only demonstrated continuity on scales longer than about 10 -26 seconds, and there is nothing to say that on shorter scales time is not in fact discrete.

Rule (b) gives the so-called Thue–Morse sequence, which we will encounter many times in this book.

For k = 2 , the number of rules that conserve the total number of black cells can be computed from q = Binomial[n, Range[0, n]] as Apply[Times, q q ] . The number of these rules that are also reversible is Apply[Times, q!]

And as we have seen several times in this book, such problems can be extremely difficult.

The digit-based approach to finding binomial coefficients modulo k has been invented independently many times since the mid-1800s, notably by Edouard Lucas in 1877 and James Glaisher in 1899.

Speculative markets Cases of markets that seem to operate almost completely independent of objective value have occurred many times in economic history, particularly in connection with innovations in technology or finance.

In the 1960s such ideas were increasingly formalized, particularly for execution times on Turing machines, and in 1965 the suggestion was made that one should consider computations feasible if they take times that grow like polynomials in their input size.

Yet looking at these patterns one notices a remarkable similarity to patterns that we have seen many times before in this book—generated by simple one-dimensional cellular automata.

Mechanisms that generally seem able to give α ≃ 1 include random walks with exponential waiting times, power-law distributions of step sizes (Lévy flights), or white noise variations of parameters, as well as random processes with exponentially distributed relaxation times (as from Boltzmann factors for uniformly distributed barrier heights), fractional integration of white noise, intermittency at transitions to chaos, and random substitution systems.