title: "Universal Turing Machine"

Universal Turing Machine

Definition. A universal Turing machine is a Turing machine $U$ that takes as input an encoded pair $\langle M, w \rangle$ and simulates $M$ on $w$, accepting exactly when $M$ accepts $w$.

$U$ keeps $M$'s tape, state, and head position written on its own tape and repeatedly consults $M$'s transition function to advance them, which is possible because $\langle M \rangle$ is just a string. One fixed machine therefore runs any machine handed to it as data, which is the stored-program computer, described by Turing in 1936. $U$ recognizes but does not decide the acceptance problem $A_{\mathsf{TM}}$: it fails to halt exactly when the machine it simulates fails to halt. Introduced in Lecture 7.