The pictures at the top of the facing page show successive steps in the evolution of an analog of their system. … All these cells are initially white, but some eventually become black—and the system is considered to halt for a particular input if the corresponding cell ever becomes black. … To set up the generalized diagonal argument one needs a way to list all possible programs.

In general the density for an arrangement of white squares with offsets v is given in s dimensions by (no simple closed formula seems to exist except for the 1 × 1 case) Product[With[{p = Prime[n]}, 1 - Length[Union[Mod[v, p]]]/p s ], {n, ∞ }] White squares correspond to lattice points that are directly visible from the origin at the top left of the picture, so that lines to them do not pass through any other integer points.

Almost all spin configurations with e[s] > - √ 2 (where here and below all quantities are divided by the total number of spins, so that -2 ≤ e[s] ≤ 2 and -1 ≤ m[s] ≤ + 1 ) yield m[s]  0 . … Of the 2 32 general 5-neighbor rules 34 conserve e[s] —but all have only very simple behavior. … The pictures at the top of the next page show the values of m[s] (densities of +1 cells) after 0, 10, 100 and 1000 steps for a 500*500 system as a function of the initial values of m[s] and e[s] .

[History of] exact solutions Some notable cases where closed-form analytical results have been found in terms of standard mathematical functions include: quadratic equations (~2000 BC) ( Sqrt ); cubic, quartic equations (1530s) ( x 1/n ); 2-body problem (1687) ( Cos ); catenary (1690) ( Cosh ); brachistochrone (1696) ( Sin ); spinning top (1849; 1888; 1888) ( JacobiSN ; WeierstrassP ; hyperelliptic functions); quintic equations (1858) ( EllipticTheta ); half-plane diffraction (1896) ( FresnelC ); Mie scattering (1908) ( BesselJ , BesselY , LegendreP ); Einstein equations (Schwarzschild (1916), Reissner–Nordström (1916), Kerr (1963) solutions) (rational and trigonometric functions); quantum hydrogen atom and harmonic oscillator (1927) ( LaguerreL , HermiteH ); 2D Ising model (1944) ( Sinh , EllipticK ); various Feynman diagrams (1960s-1980s) ( PolyLog ); KdV equation (1967) ( Sech etc.); Toda lattice (1967) ( Sech ); six-vertex spin model (1967) ( Sinh integrals); Calogero–Moser model (1971) ( Hypergeometric1F1 ); Yang–Mills instantons (1975) (rational functions); hard-hexagon spin model (1979) ( EllipticTheta ); additive cellular automata (1984) ( MultiplicativeOrder ); Seiberg–Witten supersymmetric theory (1994) ( Hypergeometric2F1 ).

At each step, this map shifts all the base 2 digits in x one position to the left. … And so after some number of steps, all the digits in x are 0, and thus the value of x is simply 0. … For the first several steps, the results as shown at the top of each corresponding picture agree.

And this has become all the more relevant as its replication with technology begins to seem realistic. But what the Principle of Computational Equivalence suggests is that abstract descriptions will never ultimately distinguish us from all sorts of other systems in nature and elsewhere. … For it implies that all the wonders of our universe can in effect be captured by simple rules, yet it shows that there can be no way to know all the consequences of these rules, except in effect just to watch and see how they unfold.

The situation is much the same as for strings—with the basic criterion just being that all replacements that appear in the rules should be for clusters of nodes that can never overlap themselves or each other. The second set of pictures below show all possible distinct clusters with up to five nodes—and all but three of these already can overlap themselves. … All possible distinct clusters containing up to five nodes, with planarity not required.

rules 0 and 128 all the cells become white, while in rule 255 all of them become black. There are also rules such as 7 and 127 in which all cells alternate between black and white on successive steps. … And it turns out that although 24 rules in all yield such nested patterns, there are only three fundamentally different forms that occur.

As the picture at the bottom of the previous page illustrates, this Turing machine emulates rule 110 in a quite straightforward way: its head moves systematically backwards and forwards, at each complete sweep updating all cells according to a single step of rule 110 evolution. … If one looks at the 4096 Turing machines with 2 states and 2 colors it is fairly easy to see that their behavior is in all cases too simple to support universality. … In all cases, all cells are initially white.

There is no doubt that they do, and as one example I will briefly discuss here what is probably the most obvious feature of essentially all financial markets: the apparent randomness with which prices tend to fluctuate. … With this view, however, it seems hard to understand why there should be any significant fluctuations in prices at all. … And it is then assumed that these estimates are ultimately affected by all sorts of events that go on in the world, making random movements