About Universality

We say an automaton is universal if it can simulate any other automaton of the same kind.

This definition depends, of course, on having suitable definitions of "simulate" and "kind", but these usually fall out naturally from the definition of the specific automaton under consideration.

Probably the most well-known example of a universal automaton is the universal Turing machine, which, given a suitably encoded input, can simulate any other Turing machine. We say that such a universal Turing machine is Turing-complete. (Pedantically, we should say that it's the set of strings that the machine accepts which is Turing-complete. But for convenience, a certain amount of abuse of notation goes on.)

Most programming languages, or at least idealized versions of them, are universal; for example, you can write a Scheme interpreter in Scheme, and then run every Scheme program you can imagine on that interpreter.

It's interesting to note that "every Scheme program you can imagine" includes that Scheme interpreter you just wrote — so you could run it on itself, and then run it on it running on it, etc, etc ad infinitum. Supporting automorphisms like this is a necessary, but not sufficient, condition for universality.

It's also interesting to note that many different kinds of automata can simulate each other: there's a Turing machine that can interpret Scheme programs, and a Scheme program that can execute Turing machines. The fact that so many different kinds of automata can simulate each other in this way, and that no one has found some automaton that none of them can simulate, leads to what's called the Church-Turing thesis. (This is arguably a kind of "universality" as well, but we stress that it is a very different sense of "universal" than what we mean in this article.)

Looking in the other direction, it's possible to show that, for many classes of automata there is no universal automaton. For example, there is no universal primitive-recursive function, no universal context-free grammar, and no universal finite-state automaton.

It is not the case that only Turing machines can be universal. There are, for example, universal cellular automata which can simulate all other cellular automata. Note as well that cellular automata are unable to simulate Turing machines, since they cannot terminate.

This last point is, incidentally, why we would argue that Wolfram's 2-3 Turing machine is not, as he claims, "simpler" than Minsky's, or Neary and Woods', universal Turing machines. Wolfram's rule 110 cellular automaton may be a universal cellular automaton, but any Turing machine which simulates it is not a universal Turing machine, because there are Turing machines which do halt, which it cannot simulate. The 2-3 machine could be made universal, perhaps, by giving it some capability to halt; but such a facility would surely increase its complexity, with no guarantee that it would still be "simpler" than the "reigning champions."