If all the points lie on a repetitive lattice each region will always be the same, and is often known as a Wigner–Seitz cell or a Dirichlet domain. … Voronoi diagrams are relevant whenever there is growth in all directions at an identical speed from a collection of seed points.

Finding layouts [for networks] One way to lay out a network g so that network distances in it come as close as possible to ordinary distances in d -dimensional space, is just to search for values of the x[i, k] which minimize a quantity such as With[{n = Length[g]}, Apply[Plus, Flatten[(Table[Distance[g, {i, j}], {i, n}, {j, n}] 2 - Table[ Sum[(x[i, k] - x[j, k]) 2 , {k, d}], {i, n}, {j, n}]) 2 ]]] using for example FindMinimum starting say with x[1, _]  0 and all the other x[_, _]  Random[] . … If one ignores all constraints beyond network distance 1, then one is in effect just trying to build the network out of identical rigid rods.

The cellular automata shown here all have 3 possible colors and nearest-neighbor rules.

Fields [and axioms] With ⊕ being + and ⊗ being × rational, real and complex numbers are all examples of fields.

(One can also construct an infinite tree from a general network by following all its possible paths, as on page 277 , but in most cases there will be no simple way to apply symbolic system rules to such a tree.)

(They thus differ from the Turing machines which Marvin Minsky and Daniel Bobrow studied in 1961 in the s = 2 , k = 2 case and concluded all had simple behavior.) … The function is total (i.e. defined for all x ) if the Turing machine always halts; otherwise it is partial (and undefined for at least some x ). … And no Turing machine of any size can directly compute a function like x 2 , 2x or Mod[x, 2] that involves manipulating all digits in x .

If one adds a ∘ b  b ∘ a to any of the other 23 axioms above then in all cases the resulting axiom system can be shown to reproduce logic. … All turn out also to work at k = 3 , but fail at k = 4 . … With 3 variables, all 32 cases with 6 Nand s are equivalent to (a ∘ b) ∘ (a ∘ (b ∘ c)) , which is axiom system (f) in the main text.

Truth and incompleteness In discussions of the foundations of mathematics in the early 1900s it was normally assumed that truth and provability were in a sense equivalent—so that all true statements could in principle be reached by formal processes of proof from fixed axioms (see page 782 ). … But the Principle of Computational Equivalence implies that in fact there are all sorts of statements that simply cannot be decided by any computational process in our universe. … Not all statements in mathematics have this kind of default truth value.

But now if one sets up a superposition of all these configurations, one can compute Mod[a # , m]& , then essentially use Fourier to find periodicities—all with a polynomial number of quantum gates. … In the mid-1990s it was thought that quantum computers might perhaps give polynomial solutions to all NP problems. But in fact only a very few other examples were found—all ultimately based on very much the same ideas as factoring.

As it happens, in each of these cases I suspect that the supposed limits are actually just associated with a lack of correct analysis of all elements of the relevant systems.