Truth and falsity [in formal systems] The notion that statements can always be classified as either true or false has been a common idealization in logic since antiquity. … An example is x + y  z , which cannot reasonably be considered either true or false unless one knows what x , y and z are. … In Mathematica functions like TrueQ and IntegerQ are set up always to yield True or False —but just by looking at the explicit structure of a symbolic expression.

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.

With s = 2 and n from 0 to 7 the number of these True for all values of variables is {0, 0, 4, 0, 80, 108, 2592, 7296} , with the first few distinct ones being (see page 781 ) {(p ⊼ p) ⊼ p, (((p ⊼ p) ⊼ p) ⊼ p) ⊼ p, (((p ⊼ p) ⊼ p) ⊼ q) ⊼ q} The number of unequal expressions obtained is {2, 3, 3, 7, 10, 15, 12, 16} (compare page 1096 ), with the first few distinct ones being {p, p ⊼ p, p ⊼ q, (p ⊼ p) ⊼ p, (p ⊼ q) ⊼ p, (p ⊼ p) ⊼ q} Most of the axioms from page 808 are too long to appear early in the list of theorems.

But it is also possible to define this function in an algebraic way f[p_, q_, r_] := Mod[p + r, 2] Algebraic definitions can also be given for other rules: • Rule 254 (page 24 ): 1 - (1 - p)(1 - q)(1 - r) • Rule 250 (page 25 ): p + r - p r • Rule 30 (page 27 ): Mod[p + q + r + q r, 2] • Rule 110 (page 32 ): Mod[(1 + p) q r + q + r, 2] In these definitions, we represent the values of cells by the numbers 1 or 0. … It is also possible to represent values of cells as True and False . And in this case cellular automaton rules become logic expressions: • Rule 254: Or[p, q, r] • Rule 250: Or[p, r] • Rule 90: Xor[p, r] • Rule 30: Xor[p, Or[q, r]] • Rule 110: Xor[Or[p, q], And[p, q, r]] (Note that Not[p] corresponds to 1 - p , And[p, q] to p q , Xor[p, q] to Mod[p + q, 2] and Or[p, q] to Mod[p q + p + q, 2] .)

Searching for logic [axioms] For axiom systems of the form {…  a} one finds: {((b ∘ b) ∘ a) ∘ (a ∘ b)  a} allows the k = 3 operator 15552 for which the Nand theorem (p ∘ p) ∘ q  (p ∘ q) ∘ q is not true. {(((b ∘ a) ∘ c) ∘ a) ∘ (a ∘ c)  a} allows the k = 4 operator 95356335 for which even p ∘ q  q ∘ p is not true. … But from any of the 23 axioms on their own I have never managed to derive p ∘ q  q ∘ p .

Rules that show complicated behavior usually do not seem to have conserved quantities, and this is true for example of rules 30, 90 and 110, at least up to blocks of length 10. … BC[a] where q is some fixed list. A way to find candidates for q is to compute NullSpace[Table[With[{u = Table[Random[Integer, {0, k - 1}], {m}]}, BC[CAStep[u]] - BC[u]], {s}]] for progressively larger m and s , and to see what lists continue to appear.

Ulam systems Having formulated the system around 1960, Stanislaw Ulam and collaborators (see page 877 ) in 1967 simulated 120 steps of the process shown below, with black cells after t steps occurring at positions Map[First, First[Nest[UStep[p[q[r[#1], #2]] &, {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}, #] &, ({#, #} &)[{{{0, 0}, {0, 0}}}], t]]] UStep[f_, os_, {a_, b_}] := {Join[a, #], #} &[f[Flatten[ Outer[{#1 + #2, #1} &, Map[First, b], os, 1], 1], a]] r[c_]:= Map[First, Select[Split[Sort[c], First[#1]  First[#2] &], Length[#]  1 &]] q[c_, a_] := Select[c, Apply[And, Map[Function[u, qq[#1, u, a]], a]] &] p[c_]:= Select[c, Apply[And, Map[Function[u, pp[#1, u]], c]] &] pp[{x_, u_}, {y_, v_}] := Max[Abs[x - y]] > 1 || u  v qq[{x_, u_}, {y_, v_}, a_] := x  y || Max[Abs[x - y]] > 1 || u  y || First[Cases[a, {u, z_}  z]]  y These rules are fairly complicated, and involve more history than ordinary cellular automata. … And as the pictures below show, this is true even just for parts of the rules above ( s alone yields outer totalistic code 686 in 2D, and rule 90 in 1D).

Given an original DNF list s , this can be done using PI[s, n] : PI[s_, n_] := Union[Flatten[ FixedPointList[f[Last[#], n] &, {{}, s}] 〚 All, 1 〛 , 1]] g[a_, b_] := With[{i = Position[Transpose[{a, b}], {0,1}]}, If[Length[i]  1 && Delete[a, i] === Delete[b, i], {ReplacePart[a, _, i]}, {}]] f[s_, n_] := With[ {w = Flatten[Apply[Outer[g, #1, #2, 1] &, Partition[Table[ Select[s, Count[#, 1]  i &], {i, 0, n}], 2, 1], {1}], 3]}, {Complement[s, w, SameTest  MatchQ], w}] The minimal DNF then consists of a collection of these prime implicants. … Given the original list s and the complete prime implicant list p the so-called Quine–McCluskey procedure can be used to find a minimal list of prime implicants, and thus a minimal DNF: QM[s_, p_] := First[Sort[Map[p 〚 # 〛 &, h[{}, Range[Length[s]], Outer[MatchQ, s, p, 1]]]]] h[i_, r_, t_] := Flatten[Map[h[Join[i, r 〚 # 〛 ], Drop[r, #], Delete[Drop[t, {}, #], Position[t 〚 All, # 〛 ], {True}]]] &, First[Sort[Position[#, True] &, t]]]], 1] h[i_, _, {}] := {i} The number of steps required in this procedure can increase exponentially with the length of p .

This can be done for blocks up to length n in a 1D cellular automaton with k colors using ReversibleQ[rule_, k_, n_] := Catch[Do[ If[Length[Union[Table[CAStep[rule, IntegerDigits[i, k, m]], {i, 0, k m - 1}]]] ≠ k m , Throw[False]], {m, n}]; True] For k = 2 , r = 1 it turns out that it suffices to test only up to n = 4 (128 out of the 256 rules fail at n = 1 , 64 at n = 2 , 44 at n = 3 and 14 at n = 4 ); for k = 2 , r = 2 it suffices to test up to n = 15 , and for k = 3 , r = 1 , up to n = 9 .

(For n < 512 , this is true when n = 1 , 2 , 3 , 4 , 6 , 7 , 9 , 15 , 22 , 28 , 30 , 46 , 60 , 63 , 127 , 153 , 172 , 303 or 471 . Maximal period is assured when in addition PrimeQ[2 n - 1] .) … The largest m less than 2 16 for which this is true is 65063, and the sequence generated in this case appears to be fairly random.