But to formulate such a question in a meaningful way one needs a notion of negation. … And as a generalization of this one can consider cases in which negation can be any operation that preserves lengths of strings.

Lower bounds [on computational complexity] If one could prove for example that P ≠ NP then one would immediately have lower bounds on all NP-complete problems. … One cannot for example sort n objects in less than about n steps since one must at least look at each object, and one cannot multiply two n -digit numbers in less than about n steps since one must at least look at each digit. … An example is testing whether one can match all possible sequences with a regular expression that involves s -fold repetitions.

Forcing nested [2D] patterns It is straightforward to find constraints that allow nested patterns; the challenge is to find ones that force such patterns to occur. Many nested patterns (such as the one made by rule 90, for example) contain large areas of uniform white, and it is typically difficult to prevent pure repetition of that area. … It then turns out that with the constraint that the only 2 × 2 arrangements of colors that can occur are ones that match these 51 blocks, one is forced to get the nested pattern below.

It took searching through a few million mobile automata to find one with behavior as complex as what we see here.

The pictures below show results for the 16 forms from page 806 , and among these one sees that logic yields the fewest theorems.

Computer language fluency It is common that when one knows a human language sufficiently well, one feels that one can readily "think in that language".

One can make an equivalent cellular automaton of larger range by having a rule in which cells at distance more than r have no effect. One can then define nearby cellular automata to be those where the differences in the rule involve only cells close to the edge of the range. With larger and larger ranges one can then construct closer approximations to continuous sequences of cellular automata.

Implementation [of basic aggregation model] One way to represent a cluster is by giving a list of the coordinates at which each black cell occurs. … The implementation above is a so-called type B Eden model in which one first selects a cell in the cluster, then randomly selects one of its neighbors. One gets extremely similar results with a type A Eden model in which one just randomly selects a cell from all the ones adjacent to the cluster.

Torsion In standard geometry, one assumes that the distance from one point to another is the same as the distance back, so that the metric tensor can be taken to be symmetric, and there is zero so-called torsion. … And if one looks at the volume of a cone this can then introduce a correction proportional to r .

Emulating discrete systems [with continuous ones] Despite it often being assumed that continuous systems are computationally more sophisticated than discrete ones, it has in practice proved surprisingly difficult to make continuous systems emulate discrete ones. … And one can set things up so that these structures exhibit the analog of attractors, and evolve towards one of a few discrete states. But the problem is that in finite time one cannot expect that they will precisely reach such states.