Live briefing
Everything about Universal Turing machine
Type of Turing machine
In computer science, a universal Turing machine (UTM) is a Turing machine capable of computing any computable sequence, as described by Alan Turing in his seminal paper "On Computable Numbers, with an Application to the Entscheidungsproblem". Or, in other words, a Turing machine that is capable of simulating any other specialized Turing machines. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Universal Turing machineA 5-minute orientation
- Skim a recent paper: A physically universal Turing machineInfluential work since 2022
- Pick up a classic book: The pattern on the stoneThe most-reprinted book on the subject
- Read the landmark paper: Small universal Turing machinesCited 132 times
- Go sideways: Turing machineA closely related topic
- Go sideways: Algorithm characterizationsA closely related topic
📖 Definitions
Noun A Turing machine capable of simulating the behavior of any Turing machine.
🏆 Landmark papers (most cited)
Small universal Turing machines
Beyond the universal Turing machine
The CNN is universal as the Turing machine
Computing exponentially faster: implementing a non-deterministic universal Turing machine using DNA
Four Small Universal Turing Machines
The CNN Universal Machine is as universal as a Turing Machine
Small fast universal Turing machines
What Turing Did after He Invented the Universal Turing Machine
🆕 Influential since 2022
📚 Books worth reading
The pattern on the stoneW. Daniel Hillis · 1998
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table…
- Algorithm characterizations Algorithm characterizations are attempts to formalize the word algorithm. Algorithm does not have a generally accepted formal definition. Researchers are…
- Description number Description numbers are numbers that arise in the theory of Turing machines. They are very similar to Gödel numbers, and are also occasionally called "Gödel…
- Random-access stored-program machine In theoretical computer science the random-access stored-program (RASP) machine model is an abstract machine used for the purposes of algorithm development…
- Theory of computation In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation…
- Turing machine equivalents A Turing machine is a hypothetical computing device, first conceived by Alan Turing in 1936. Turing machines manipulate symbols on a potentially infinite…
- Read-only Turing machine A read-only Turing machine or two-way deterministic finite-state automaton (2DFA) is class of models of computability that behave like a standard Turing…
- Computable function Computable functions are the basic objects of study in computability theory. Informally, a function is computable if there is an algorithm that computes…