Notes

Chapter 11: The Notion of Computation

Section 12: Universality in Turing Machines and Other Systems


Testing universality [in symbolic systems]

One can tell that a symbolic system is universal if one can find expressions that act like the s and k combinators, so that, for example, for some expression e, e[x][y][z] evolves to x[z][y[z]].


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