"Universal machine" redirects here. For other uses, see Universal machine (disambiguation).
Turing machines
Machine
Turing machine equivalents
Turing machine examples
Turing machine gallery
Variants
Alternating Turing machine
Neural Turing machine
Nondeterministic Turing machine
Quantum Turing machine
Post–Turing machine
Probabilistic Turing machine
Multitape Turing machine
Multi-track Turing machine
Symmetric Turing machine
Total Turing machine
Unambiguous Turing machine
Universal Turing machine
Zeno machine
Science
Alan Turing
Category:Turing machine
v
t
e
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 man 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 . .... qI; 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]
Alan Turing introduced the idea of such a machine in 1936–1937. This principle is considered to be the origin of the idea of a stored-program computer used by John von Neumann in 1946 for the "Electronic Computing Instrument" that now bears von Neumann's name: the von Neumann architecture.[4]
^Turing (1937), p. 241.
^Turing (1937), p. 231.
^Turing (1937), p. 232.
^Davis (2018), p. [page needed].
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).
and 21 Related for: Universal Turing machine information
computer science, a universalTuringmachine (UTM) is a Turingmachine capable of computing any computable sequence, as described by Alan Turing in his seminal...
calculus. A Turingmachine that is able to simulate any other Turingmachine is called a universalTuringmachine (UTM, or simply a universalmachine). Another...
simulate a Turingmachine, it is Turing equivalent to a Turingmachine. A universalTuringmachine can be used to simulate any Turingmachine and by extension...
A quantum Turingmachine (QTM) or universal quantum computer is an abstract machine used to model the effects of a quantum computer. It provides a simple...
probabilities for the transitions, probabilistic Turingmachines can be defined as deterministic Turingmachines having an additional "write" instruction where...
A Turingmachine is a hypothetical computing device, first conceived by Alan Turing in 1936. Turingmachines manipulate symbols on a potentially infinite...
In theoretical computer science, a nondeterministic Turingmachine (NTM) is a theoretical model of computation whose governing rules specify more than...
computational complexity theory, an alternating Turingmachine (ATM) is a non-deterministic Turingmachine (NTM) with a rule for accepting computations that...
A neural Turingmachine (NTM) is a recurrent neural network model of a Turingmachine. The approach was published by Alex Graves et al. in 2014. NTMs combine...
to supplement the article Turingmachine. The following table is Turing's very first example (Alan Turing 1937): "1. A machine can be constructed to compute...
Zeno machines (abbreviated ZM, and also called accelerated Turingmachine, ATM) are a hypothetical computational model related to Turingmachines that...
encoding for Turingmachines, where an encoding is a function which associates to each TuringMachine M a bitstring <M>. If M is a TuringMachine which, on...
super-Turing computation is a set of hypothetical models of computation that can provide outputs that are not Turing-computable. For example, a machine that...
Turingmachine starting from a given state ever print a given symbol?") and to the printing problem considered in Turing's 1936 paper ("does a Turing...
completeness in the sense of computational universality. Specifically, a Turingmachine is a universalTuringmachine if its halting problem (i.e., the set...
In computability theory, the UTM theorem, or universalTuringmachine theorem, is a basic result about Gödel numberings of the set of computable functions...
The Turing test, originally called the imitation game by Alan Turing in 1950, is a test of a machine's ability to exhibit intelligent behaviour equivalent...
by Alan Turing in his seminal 1936 paper, On Computable Numbers. Turing proposed a simple device that he called "Universal Computing machine" and that...