Notes

Chapter 12: The Principle of Computational Equivalence

Section 9: Implications for Mathematics and Its Foundations


Symbolic systems [and operator systems]

By introducing constants (0-argument operators) and interpreting as function application one can turn any symbolic system such as e[x][y]->x[x[y]] from page 103 into an algebraic system such as (e ∘ a) ∘ b == a ∘ (a ∘ b). Doing this for the combinator system from page 711 yields the so-called combinatory algebra {((s ∘ a) ∘ b) ∘ c == (a ∘ c) ∘ (b ∘ c), (k ∘ a) ∘ b == a}.


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