Universal Turing machine

In computer science, a universal Turing machine (UTM) is a Turing machine capable of computing any computable sequence,^[1] as described by Alan Turing in his seminal paper "On Computable Numbers, with an Application to the Entscheidungsproblem". Common sense might say that a universal machine is impossible, but Turing proves that it is possible.^[a] 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 ⁠${\displaystyle q_{1},q_{2},\dots ,q_{R}}$⁠; which will be called "m-configurations".^[2] He then described the operation of such machine, as described below, and argued:

It is my contention that these operations include all those which are used in the computation of a number.^[3]

Turing introduced the idea of such a machine in 1936–1937.

Cite error: There are <ref group=lower-alpha> tags or {{efn}} templates on this page, but the references will not show without a {{reflist|group=lower-alpha}} template or {{notelist}} template (see the help page).