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 $<M>$ the encoding of machine $M$ as a binary string, then we have $U(<M>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
Canonical name	UniversalTuringMachine
Date of creation	2013-03-22 13:43:46
Last modified on	2013-03-22 13:43:46
Owner	tromp (1913)
Last modified by	tromp (1913)
Numerical id	7
Author	tromp (1913)
Entry type	Definition
Classification	msc 68Q05
Related topic	ArtificialInteglligence
Related topic	StrongAIThesis