Related [texture perception] models Rather than requiring particular templates to be matched, one can consider applying arbitrary cellular automaton rules.

Note that of the 8 cases in the basic rule for rule 110, only one differs from rule 102—which is a simple additive rule obtained by reflecting rule 60.

Pointer-based encoding One can encode a list of data d by generating pointers to the longest and most recent copies of each subsequence of length at least b using PEncode[d_, b_ : 4] := Module[{i, a, u, v}, i = 2; a = {First[d]}; While[i ≤ Length[d], {u, v} = Last[Sort[Table[{MatchLength[d, i, j], j}, {j, i - 1}]]]; If[u ≥ b, AppendTo[a, p[i - v, u]]; i += u, AppendTo[a, d 〚 i 〛 ]; i++]]; a] MatchLength[d_, i_, j_] := With[{m = Length[d] - i}, Catch[ Do[If[d 〚 i + k 〛 =!… One can reproduce the original data using PDecode[a_] := Module[{d = Flatten[ a /. p[j_, r_]  Table[p[j], {r}]]}, Flatten[MapIndexed[ If[Head[#1] === p, d 〚 #2 〛 = d 〚 #2 - First[#1] 〛 ,#1] &, d]]] To get a representation purely in terms of 0 and 1, one can use a self-delimiting representation for each integer that appears. (Knowing the explicit representation one could then determine whether each block would be shorter if encoded literally or using a pointer.)

But as soon as there is even one arbitrary predicate with two arguments the system becomes universal (see page 784 ). And indeed this is the case even if one considers only statements with quantifiers ∀ ∃ ∀ . (The system is also universal with one two-argument function or two one-argument functions.)

Probabilistic estimates [of cellular automaton properties] One way to get estimates for density and other properties of class 3 cellular automata is to make the assumption that the color of each cell at each step is completely random. … One can systematically include more such correlations by looking at more steps of evolution at once. … (For rules 90 and 30 the functions obtained after one step are respectively 2 p (1 - p) and p (2 p 2 - 5 p + 3) , both of which turn out to imply correct final densities of 1/2 ).

But as soon as one looks at a picture of how rule 110 actually behaves, the idea that it could be universal starts to seem much less absurd. … And from pictures like the one on the facing page , it begins to seem not unreasonable that perhaps these localized structures could be arranged so as to perform meaningful computations.

Randomness [in tag systems] To get some idea of the randomness of the behavior, one can look at the sequence of first elements produced on successive steps.

Probabilistic cellular automata As an alternative to having continuous values at each cell, one can consider ordinary cellular automata with discrete values, but introduce probabilities for, say, two different rules to be applied at each cell.

Planck length Even in existing particle physics it is generally assumed that the traditional simple continuum description of space must break down at least below about the Planck length Sqrt[ℏ G/c 3 ] ≃ 2 × 10 -35 meters—since at this scale dimensional analysis suggests that quantum effects should be comparable in magnitude to gravitational ones.

But it turns out that this is no longer true if one allows systems which themselves can access the oracle in the course of their evolution. Yet one can then imagine a higher-level oracle for these systems, and indeed a whole hierarchy of levels of oracles—as studied in the theory of degrees of unsolvability.