In 1979 Matiyasevich also showed that universality could be achieved with an exponential Diophantine equation with many terms, but with only 3 variables. … It is even conceivable that a Diophantine equation with 2 variables could be universal: with one variable essentially being used to represent the program and input, and the other the execution history of the program—with no finite solution existing if the program does not halt.

And as I argue in the main text, it is in fact only for the rather limited kinds of mathematics that have historically been pursued that such proofs can be expected to be sufficient.

Note (a) for Systems of Limited Size and Class 2 Behavior…Using the result that (1 + x 2 m )  (1 + x) 2 m modulo 2 for any m , one then finds that the repetition period always divides the quantity p[n]=2^MultiplicativeOrder[2, n] - 1 , which in turn is at most 2 n-1 -1 . The actual periods are often smaller than p[n] , with the following ratios occurring: There appears to be no case for n>5 where the period achieves the absolute maximum 2 n-1 -1 . … And now the repetition period for odd n divides q[n]=2^MultiplicativeOrder[2, n, {1,-1}] - 1 The exponent here always lies between Log[k, n] and (n-1)/2 , with the upper bound being attained only if n is prime.

And although statistical significance is reduced by considering only discrete features, some evidence has emerged that different species do indeed have shapes related by changes in fairly small numbers of geometrical parameters.

But as noted by Donald Knuth and Peter Bendix in 1970 it turns out often to be sufficient just iteratively to add new rules only for each so-called critical pair q , r that is obtained from strings p that represent minimal overlaps in the left-hand sides of the rules one has.

One feature of relativity is that it implies that only relative motion is ultimately ever detectable.

Gauge invariance It is often convenient to define quantities for which only differences or derivatives matter.

. • 1200s: Fibonacci sequences, Pascal's triangle and other rule-based numerical constructions are studied, but are found to show only simple behavior. • 1500s: Leonardo da Vinci experiments with rules corresponding to simple geometrical constraints (see page 875 ), but finds only simple forms satisfying these constraints. • 1700s: Leonhard Euler and others compute continued fraction representations for numbers with simple formulas (see pages 143 and 915 ), noting regularity in some cases, but making no comment in other cases. • 1700s and 1800s: The digits of π and other transcendental numbers are seen to exhibit apparent randomness (see page 136 ), but the idea of thinking about this randomness as coming from the process of calculation does not arise. • 1800s: The distribution of primes is studied extensively—but mostly its regularities, rather than its irregularities, are considered. … (See page 1088 .) • 1960, 1967: Stanislaw Ulam and collaborators simulate systems close to 2D cellular automata, and note the appearance of complicated patterns (see above ). • 1961: Edward Fredkin simulates the 2D analog of rule 90 and notes features that amount to nesting (see above ). • Early 1960s: Students at MIT try running many small computer programs, and in some cases visualizing their output. They discover various examples (such as "munching foos") that produce nested behavior (see page 871 ), but do not go further. • 1962: Marvin Minsky and others study many simple Turing machines, but do not go far enough to discover the complex behavior shown on page 81 . • 1963: Edward Lorenz simulates a differential equation that shows complex behavior (see page 971 ), but concentrates on its lack of periodicity and sensitive dependence on initial conditions. • Mid-1960s: Simulations of random Boolean networks are done (see page 936 ), but concentrate on simple average properties. • 1970: John Conway introduces the Game of Life 2D cellular automaton (see above ). • 1971: Michael Paterson considers a class of simple 2D Turing machines that he calls worms and that exhibit complicated behavior (see page 930 ). • 1973: I look at some 2D cellular automata, but force the rules to have properties that prevent complex behavior (see page 864 ). • Mid-1970s: Benoit Mandelbrot develops the idea of fractals (see page 934 ), and emphasizes the importance of computer graphics in studying complex forms. • Mid-1970s: Tommaso Toffoli simulates all 4096 2D cellular automata of the simplest type, but studies mainly just their stabilization from random initial conditions. • Late 1970s: Douglas Hofstadter studies a recursive sequence with complicated behavior (see page 907 ), but does not take it far enough to conclude much. • 1979: Benoit Mandelbrot discovers the Mandelbrot set (see page 934 ) but concentrates on its nested structure, not its overall complexity. • 1981: I begin to study 1D cellular automata, and generate a small picture analogous to the one of rule 30 on page 27 , but fail to study it. • 1984: I make a detailed study of rule 30, and begin to understand the significance of it and systems like it.

Almost without exception, however, the rules have in the past been chosen to yield only rather specific and simple results. … Although paperfolding has presumably been practiced for at least 2000 years, even the nested form on page 892 seems to have been noticed only very recently. … Various attempts to enumerate all possible patterns of particular simple kinds have been made—a notable example being Sébastien Truchet in 1704 drawing 2D patterns formed by combining , , , in various possible ways.

For n = 3 this polytope comes close to filling the region of all possible colors, but for no n can it completely fill it—which is why practical displays and printing processes can produce only limited ranges of colors.