For any input x one can test whether the machine will ever halt using u[{Reverse[IntegerDigits[x, 2]], 0}] u[list_] := v[Split[Flatten[list]]] v[{a_, b_: {}, c_: {}, d_: {}, e_: {}, f_: {}, g___}] := Which[a == {1} || First[a]  0, True, c  {}, False, EvenQ[Length[b]], u[{a, 1 - b, c, d, e, f, g}], EvenQ[Length[c]], u[{a, 1 - b, c, 1, Rest[d], e, f, g, 0}], e  {} || Length[d] ≥ Length[b] + Length[a] - 2, True, EvenQ[Length[e]], u[{a, b , c, d, f, g}], True, u[{a, 1 - b, c, 1 - d, e, 1, Rest[f], g, 0}]] This test takes at most n/3 recursive steps, even though the original machine can take of order n 2 steps to halt.

This is certainly not true for every substitution system. … Essentially what needs to be true is that the sequence of elements alone must always uniquely determine what replacements can be made in every part of the system.

The idea is to set up an arithmetic statement that can be proved true if the evolution of a cellular automaton from a given initial condition makes a given cell be a given color at a given step, and can be proved false if it does not. … Such universality then implies Gödel's Theorem and shows that there must exist statements about arithmetic that cannot ever be proved true or false from its normal axioms.

As the picture below shows, there are 16 different possible operators that take two arguments and allow two values, say true and false. … Black stands for True ; white for False .

Predicate logic Basic logic in effect concerns itself with whole statements (or "propositions") that are each either True or False . … In general statements in predicate logic can contain arbitrary so-called predicates, say p[x] or r[x, y] , that are each either True or False for given x and y . … In basic logic any statement that is true for all possible assignments of truth values to variables can always be proved from the axioms of basic logic.

The theorems are respectively: (1), (2) idempotence (laws of tautology) of And and Or, (3), (4) commutativity of And and Or, (5) law of double negation, (6), (7) absorption (redundancy) laws, (8) law of noncontradiction (definition of False), (9) law of excluded middle (definition of True), (10) de Morgan's law, (11), (12) associativity of And and Or, (13), (14) distributive laws.

The translation from the Turing machine problem is achieved by representing the behavior of the Turing machine by saying which of a sequence of elementary statements are true about it at each step: whether the head is in one state or another, whether the cell under the head is black or white, and whether the head is at each of the possible positions it can be in. The Boolean expression then gives constraints on which of these statements can simultaneously be true.

reached—corresponding to the fact that statements must exist that cannot be proved either true or false from a given set of axioms. … And the same is true of group theory and other algebraic systems like ring theory.

The Relationship of Space and Time To make an ultimate theory of physics one needs to understand the true nature not only of space but also of time. … But for most of the systems based on programs that I have discussed in this book this is certainly not true.

possible strings of a given length are eventually generated if one starts from the string representing "true". … For if one looks at axiom systems that are widely used in mathematics they almost all tend to be complete enough to prove at least a fair fraction of statements either true or false.