Chapter 12: The Principle of Computational Equivalence

Section 9: Implications for Mathematics and Its Foundations

Operator systems

One can represent the possible values of expressions like f[f[p,q],p] by rule numbers analogous to those used for cellular automata. Specifying an operator f (taken in general to have n arguments with k possible values) by giving the rule number u for f[p,q, …], the rule number for an expression with variables vars can be obtained from

With[{m = Length[vars]}, FromDigits[ Block[{f = Reverse[IntegerDigits[u, k, kn]][[FromDigits[ {##}, k] + 1]] &}, Apply[Function[Evaluate[vars], expr], Reverse[Array[IntegerDigits[# - 1, k, m] &, km]], {1}]], k]]

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