Universal Turing machine

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a universal Turing machine (UTM) is a <a href="/facts/Turing_machine/ojCtglYu">Turing machine</a> capable of computing any computable sequence, as described by <a href="/facts/Alan_Turing/klov9b6g">Alan Turing</a> in his seminal paper "On Computable Numbers, with an Application to the <a href="/facts/Entscheidungsproblem/y8LDal2X">Entscheidungsproblem</a>". Common sense might say that a universal machine is impossible, but Turing proves that it is possible. He suggested that we may compare a human in the process of computing a real number to a machine which is only capable of a finite number of conditions ⁠
 
 
 
 
 q
 
 1
 
 
 ,
 
 q
 
 2
 
 
 ,
 …
 ,
 
 q
 
 R
 
 
 
 
 {\displaystyle q_{1},q_{2},\dots ,q_{R}}
 
⁠; which will be called "m-configurations". He then described the operation of such machine, as described below, and argued:

<blockquote>It is my contention that these operations include all those which are used in the computation of a number. </blockquote>
<a href="/facts/Alan_Turing/klov9b6g">Turing</a> introduced the idea of such a machine in 1936–1937.

Universal Turing machine open-in-new

Universal Turing machine