# universal Turing machine

A universal Turing machine $U$ is a Turing machine with a single binary one-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 must be prefix-free, so that no special end-marker or ‘blank’ is needed to recognize a code’s end. Having transferred the description of $M$ onto its worktape, $U$ then proceeds to simulate the behaviour of $M$ on the remaining contents 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 $U(x)=M(x)$.

There are two kinds of universal Turing machine, depending on whether the input tape alphabet of the simulated machine is $\{0,1,\#\}$ 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 property that the set of inputs on which it halts is prefix free.

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

Title universal Turing machine UniversalTuringMachine 2013-03-22 13:43:46 2013-03-22 13:43:46 tromp (1913) tromp (1913) 7 tromp (1913) Definition msc 68Q05 ArtificialInteglligence StrongAIThesis