# 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 $$.

There are two kinds of universal Turing machine, depending on whether the input 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 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 |