Editing Universal Turing machine (section)

==Mathematical theory==
With this encoding of action tables as strings, it becomes possible, in principle, for Turing machines to answer questions about the behaviour of other Turing machines. Most of these questions, however, are [[Undecidable problem|undecidable]], meaning that the function in question cannot be calculated mechanically. For instance, the problem of determining whether an arbitrary Turing machine will halt on a particular input, or on all inputs, known as the [[Halting problem]], was shown to be, in general, undecidable in Turing's original paper. [[Rice's theorem]] shows that any non-trivial question about the output of a Turing machine is undecidable.

A universal Turing machine can calculate any [[computable function|recursive function]], decide any [[recursive language]], and accept any [[recursively enumerable language]]. According to the [[Church–Turing thesis]], the problems solvable by a universal Turing machine are exactly those problems solvable by an ''[[algorithm]]'' or an ''effective method of computation'', for any reasonable definition of those terms.  For these reasons, a universal Turing machine serves as a standard against which to compare computational systems, and a system that can simulate a universal Turing machine is called [[Turing complete]].

An abstract version of the universal Turing machine is the [[Utm theorem|universal function]], a computable function which can be used to calculate any other computable function. The [[UTM theorem]] proves the existence of such a function.