universal Turing machine

A universal Turing machine $U$ is a Turing machine with a single binaryone-way read-only input tape, on which it expects to find the encoding of an arbitrary Turing machine $M$. The set of all Turing machine encodings mustbe prefix-free, so that no special end-marker or ‘blank’ is needed to recognizea code’s end. Having transferred the description of $M$ onto its worktape,$U$ then proceeds to simulate the behaviour of $M$ on the remainingcontents of the input tape. If $M$ halts, then $U$ cleans up its worktape,leaving it with just the output of $M$, and halts too.

If we denote by $M()$ the partial function computed by machine $M$,and by the encoding of machine $M$ as a binary string,then we have .

There are two kinds of universal Turing machine, depending on whether theinput tape alphabet of the simulated machine is $\{0,1,\mathrm{\#}\}$ or just $\{0,1\}$.The first kind is a plain Universal Turing machine;while the second is a prefix Universal Turing machine,which has the nice propertythat the set of inputs on which it halts is prefix free.

The letter $U$ is commonly used to denote a fixed universal machine, whosetype is either mentioned explicitly or assumed clear from context.