Notes

Chapter 12: The Principle of Computational Equivalence

Section 9: Implications for Mathematics and Its Foundations


Equivalential calculus

Expressions with variables vars are equivalent if they give the same results for

Mod[Map[Count[expr, #, {-1}] &, vars], 2]

With n variables, there are thus 2^n equivalence classes of expressions (compared to 2^2^n for ordinary logic). The operator can be either Xor or Equal (6 or 9). With k=3 there are no operators that yield the same results; with k=4 {458142180, 1310450865, 2984516430, 3836825115} work (see below). The shortest axiom system that works up to k=2 is {(a · b) · a == b}. With modus ponens as the rule of inference, the shortest single-axiom system that works is known to be {(a · b) · ((c · b) · (a · c))}. Note that equivalential calculus describes the smallest non-trivial group, and can be viewed as an extremely minimal model of algebra.


From Stephen Wolfram: A New Kind of Science [citation]