In the case of both simple and completely random images, many features are recognizable even with fairly few basic forms—implying that a highly compressed representation can be given.

For example, in a generalized Ising model (see page 944 ) for a spin system the undecidability of the tiling problem implies that it is undecidable whether a given energy function leads to a phase transition in the infinite size limit. Somewhat similarly, the undecidability of equivalence of 4-manifolds implies undecidability of questions about quantum gravity models.

For both regular and context-free languages the so-called pumping lemmas imply that if any finite sequences satisfy the constraints, then so must an essentially repetitive infinite sequence.

And with such a definition, confluence is what is needed to obtain transitivity for equality, so that p  q and q  r implies p  r . … If a terminating multiway system has the confluence property, then this implies that regardless of the path taken, a given string will always evolve to a unique string that can be thought of as giving a canonical or normal form for the original string. … Showing only the arguments to f , the pictures below illustrate how the flat functions Xor and And are confluent, while the non-flat function Implies is not.

But in fact, much as in the case of time travel, such connections do not represent additional observable effects; they simply imply consistency conditions, in this case between universes whose paths converge.

But the results of this section imply that for complexity this is not the case.

And this implies that it is possible to construct for example a mobile automaton which emulates the universal cellular automata that we discussed a couple of sections ago.

In 1936, however, Gerhard Gentzen showed that the axioms of set theory imply the consistency of Peano arithmetic (see page 1160 ).

Instead, the possibility of motion that leads to earlier times simply implies a requirement of consistency between behavior at earlier and later times.

And at least in a linear approximation any given PDE then typically implies that ω is connected to the wavenumber k by a so-called dispersion relation, which often has a simple algebraic form. … But particularly when the original PDE is nonlinear one often finds that Im[ ω ] < 0 for some range of k —implying an instability which causes modes with certain spatial wavelengths to grow.