But as soon as one introduces actual axioms that constrain the operators this is no longer true—and in general it can be undecidable whether or not a particular equivalence holds.

With black and white interpreted as True and False , the forms of operators shown here correspond respectively to And , Equal , Implies and Nand .

Physical randomness generators It is almost universally assumed that at some level physical processes must be the best potential sources of true randomness.

Implementation [of conserved quantity test] Whether a k -color cellular automaton with range r conserves total cell value can be determined from Catch[Do[ (If[Apply[Plus, CAStep[rule, #] - #] ≠ 0, Throw[False]] &)[ IntegerDigits[i, k, m]], {m, w}, {i, 0, k m - 1}]; True] where w can be taken to be k 2r , and perhaps smaller.

Complements of recursively enumerable sets are characteristically associated with Π 1 statements of the form ∀ t ϕ [t] —an example being whether a given system never halts. ( Π 1 and Σ 1 statements are such that if they can be shown to be undecidable, then respectively they must be true or false, as discussed on page 1167 .) … (Showing that a statement with n ≥ 1 is undecidable does not establish that it is always true or always false.)

[Mathematical] proofs in practice At some level the purpose of a proof is to establish that something is true. … For while they make it easy at a formal level to check that certain statements are true, they do little at a more conceptual level to illuminate why this might be so.

As discussed on page 351 , however, it seems likely that in nature true minima are very rare, and that instead what is usually seen are just the results of actual dynamical processes of evolution.

The same is true even if one allows a small fraction of squares to violate the constraints.

But as discussed on page 786 , nothing similar is true for equations involving only integers, and in this case finding solutions can in effect require following the evolution of a system like a cellular automaton for infinitely many steps.

However, no specific value of h for which this is true has ever been explicitly found.