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 2n equivalence classes of expressions (compared to 22n 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.



Image Source Notebooks:

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