The Universal Turing Machine

The rationale for a universal Turing machine

The Turing machines we have seen so far are single-purpose automata—they only solve one problem or accept one language. Alan Turing went beyond that in his research to define a universal machine, a $\text{TM}$ capable of simulating any other $\text{TM}$. The universal Turing machine $\text{(UTM)}$ takes two inputs: a symbolic encoding of another machine and an input string. It then simulates the execution of the input machine on the input string and yields the result of that execution. This should sound familiar—that’s exactly how general-purpose computers operate, and the $\text{UTM}$ is where the idea of a stored-program computing mechanism originated. In other words, programs are just strings (rendered in some encoding) fed into a computer, and the computer runs the program on whatever input we give it.

Note: Just as a Turing machine models a specific computational process, the universal Turing machine models a computer.

Converting a Turing machine for use in a UTM

Recall that the operation of a $\text{TM}$ is defined by its transition function, $\delta$. Each element in $\delta$ is a pairing of two inputs with three outputs, which we can represent as a 5-tuple. For example, the transition $\delta(q_0,a)=(q_1,b,\to)$ can be represented in text by the string “$q_0,a,q_1,b,R$”.

Now let’s consider how to write a program to act as a $\text{UTM}$ using such input. Our program needs to know the start state, the halt state(s), and each transition in $\delta$.