The 3n+1 problem The system described here is similar to the so-called 3n+1 problem, in which one looks at the rule n  If[EvenQ[n], n/2, (3n + 1)/2] and asks whether for any initial value of n the system eventually evolves to 1 (and thereafter simply repeats the sequence 1, 2, 1, 2, ...). … An alternative formulation is to ask whether for all n FixedPoint[(3#/2^IntegerExponent[#, 2] + 1)/2 &, n]  2 With the rule n  If[EvenQ[n], 5n/2, (n + 1)/2] used in the main text, the sequence produced repeats if n ever reaches 2, 4 or 40 (and possibly higher numbers). But with initial values of n up to 10,000, this happens in only 642 cases, and with values up to 100,000 it happens in only 2683 cases.

Indeed, essentially the only problem on which cryptography systems have so far successfully been based is factoring of integers (see below ).

Yet for ordinary physical objects we are used to the idea that they remember little of their history, for at a macroscopic level we tend to see only the coarsest traces.

And indeed the question of whether the halting times for a system grow only like a power of input size is in general undecidable.

(Unlike Hilbert's axioms they require only first-order predicate logic.)

(Modern English has only the compound form neither ... nor .)

In the late 1800s there were efforts—notably by Richard Dedekind and Georg Cantor —to set up a general theory of real numbers relying only on basic concepts about integers—and these efforts led to set theory. … (Note that with n variables the number of steps needed can increase like 2 2 n .)

So-called hyperbolic equations (such as the wave equation, the sine-Gordon equation and my equation) work a little like cellular automata in that in at least one dimension information can propagate only at a limited speed, say c . The result is that in such equations, giving values for u[t, x] at t = 0 for -s < x < s will uniquely determine u[t, x] at larger t for -s + c t < x < s - c t . In other PDEs, such as so-called elliptic ones, there is no such limit on the rate of information propagation, and as a result, it is immediately necessary to know values of u[t, x] at all x , and on the boundaries of the region, in order to determine u[t, x] for any t > 0 .

In systems like mobile automata and Turing machines the colors of initial cells can be random, but the active cell must start at a definite location, and depending on the behavior only a limited region of initial cells near this location may ever be sampled.

The same is true of the right-hand edge in rule 30—though the left-hand edge in this case expands only about 0.2428 cells on average per step. In rule 22, both edges expand about 0.7660 cells on average per step. … (For rule 45, the left-hand edge of the difference pattern moves about 0.1724 cells per step; for rule 54 both edges move about 0.553 cells per step.)