Despite some confusion in the literature, however, this procedure can reproduce only a tiny fraction of all possible nested patterns.

Structures [in rule 110] The persistent structures shown can be obtained from the following {n, w} by inserting the sequences IntegerDigits[n, 2, w] between repetitions of the background block b : {{152, 8}, {183, 8}, {18472955, 25}, {732, 10}, {129643, 18}, {0, 5}, {152, 13}, {39672, 21}, {619, 15}, {44, 7}, {334900605644, 39}, {8440, 15}, {248, 9}, {760, 11}, {38, 6}} The repetition periods and distances moved in each period for the structures are respectively {{4, -2}, {12, -6}, {12, -6}, {42, -14}, {42, -14}, {15, -4}, {15, -4}, {15, -4}, {15, -4}, {30, -8}, {92, -18}, {36, -4}, {7, 0}, {10, 2}, {3, 2}} Note that the periodicity of the background forces all rule 110 structures to have periods and distances given by {4, -2} r + {3, 2} s where r and s are non-negative integers.

Almost all electronic devices also exhibit a third kind of noise, whose main characteristic is that its spectrum is not flat, but instead goes roughly like 1/f over a wide range of frequencies.

Diophantine equations If variables appear only linearly, then it is possible to use ExtendedGCD (see page 944 ) to find all solutions to any system of Diophantine equations—or to show that none exist. … Just as for all sorts of other systems with complex behavior, some idea of overall properties of Diophantine equations can be found on the basis of an approximation of perfect randomness. … If one wants to enumerate all possible Diophantine equations there are many ways to do this, assigning different weights to numbers of variables, and sizes of coefficients and of exponents.

But Gödel then took the crucial step of showing that the process of finding outputs from all such procedures could in effect be viewed as equivalent to following relations of logic and arithmetic—thus establishing that these relations are in a certain sense universal (see page 784 ). This fact, however, was embedded inside the rather technical proof of Gödel's Theorem, and it was at first not at all clear how specific it might be to the particular mathematical systems considered.

Some concentrate on specific nearby stars, while others look at the whole sky, or test the stream of data from all observations at a particular radio telescope, sometimes scanning for repetitive trains of pulses rather than single frequencies. … The detection distance increases like the square root of the signal strength, covering all 10 11 stars in our galaxy when the signal uses the total power output of a star.

[History of] Church's Thesis The idea that any computation that can be done at all can be done by a universal system such as a universal Turing machine is often referred to as Church's Thesis. … From the 1940s to 1960s many different types of systems—almost all mentioned at some point or another in this book—were shown to be equivalent in their computational capabilities.

But in the summer of 1981 I did what I considered to be a fairly straightforward computer experiment to see how all programs of a particular type behaved.

Computer experiments Essentially all the computer experiments for this book were done using Mathematica running on a standard workstation-class computer, and later PC (initially on a 33 MHz NeXTstation, then on a 100 MHz HP 700 running NeXTSTEP, then on a 200 MHz P6 PC running Windows 95, and finally on 450 MHz, 700 MHz and faster PCs running Windows 95, and later Windows NT—with a Linux fileserver).

Normally one specifies the first n inputs, taking the others to be fixed, and then looks say at the first output, ignoring all others.