universal Turing machine
A universal Turing machine 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 . 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 onto its worktape, then proceeds to simulate the behaviour of on the remaining contents of the input tape. If halts, then cleans up its worktape, leaving it with just the output of , and halts too.
There are two kinds of universal Turing machine, depending on whether the input tape alphabet of the simulated machine is or just . 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.
|Title||universal Turing machine|
|Date of creation||2013-03-22 13:43:46|
|Last modified on||2013-03-22 13:43:46|
|Last modified by||tromp (1913)|