Notes

Chapter 12: The Principle of Computational Equivalence

Section 9: Implications for Mathematics and Its Foundations


Encodings of arithmetic [by different operations]

Statements in arithmetic are normally written in terms of +, × and Δ (and logical operations). But it turns out also to be possible to encode such statements in terms of other basic operations. This was for example done by Julia Robinson in 1949 with Δ (or a+1) and Mod[a,b]==0. And in the 1990s Ivan Korec and others showed that it could be done just with Mod[Binomial[a+b, a], k] with k=6 or any product of primes—and that it could not be done with k a prime or prime power. These operations can be thought of as finding elements in nested Pascal's triangle patterns produced by k-color additive cellular automata. Korec showed that finding elements in the nested pattern produced by the k=3 cellular automaton with rule {{1, 1, 3}, {2, 2, 1}, {3, 3, 2}}[[#1, #2]]& (compare page 886) was also enough.


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