Minimal theories Particularly in fundamental physics it has been found that the correct theory is often the minimal one consistent with basic observations.

But if one allows oneself to generate the object in any way at all, this may still be easy, even if P !

[History of] numbering scheme I introduced the numbering scheme used here in the 1983 paper where I first discussed one-dimensional cellular automata (see page 881 ).

And the reason is that one can generate the elements in it by effectively maintaining a copy of the Turing machine for each possible initial condition, then following a procedure where for example at step n one updates the one for initial condition IntegerExponent[n, 2] , and watches to see if it halts.

With a single two-argument operator (such as ∘ ) what one has is in general known as a groupoid (though this term means something different in topology and category theory); with two such operators a ringoid. … But the number of systems that have traditionally been studied in mathematics and that are known to require only one 2-argument operator are fairly limited. … One can nevertheless generalize say to polyadic groups, with 3-argument composition and analogs of associativity such as f[f[a, b, c], d, e]  f[a, f[b, c, d], e]  f[a, b, f[c, d, e]] Another example is the cellular automaton axiom system of page 794 ; see also page 886 .

In 1900, as one of his list of 23 important mathematical problems, David Hilbert posed the problem of finding a single finite procedure that could systematically determine whether a solution exists to any specified Diophantine equation. … It had been known since the 1930s that any Diophantine equation can be reduced to one with degree 4—and in 1980 James Jones showed that a universal Diophantine equation with degree 4 could be constructed with 58 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.

No single shape is known which has the property that it can tile the plane only non-repetitively, although one strongly suspects that one must exist. … In addition, in no case has a simple set of tiles been found which force a pattern more complicated than a nested one.

One starts by converting the list of cell colors at each step to a polynomial FromDigits[list, x] . … The state z = 1 evolves after one step to the state z = 1 + x , and for odd n this latter state always eventually appears again. 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 .

Spacetime patches [in cellular automata] One can imagine defining entropies and dimensions associated with regions of any shape in the spacetime history of a cellular automaton. As an example, one can consider patches that extend x cells across in space and t cells down in time. … One can define a topological spacetime entropy h tx as Limit[Limit[Log[k, s[t, x]]/t , t  ∞ ], x  ∞ ] and a measure spacetime entropy h μ tx by replacing s with p Log[p] .

History [of reversal-addition systems] Systems similar to the one described here (though often in base 10) were mentioned in the recreational mathematics literature at least as long ago as 1939.