Turing machine
E2505
abstract computational model
automaton
formal system
mathematical model of computation
theoretical computer science concept
A Turing machine is an abstract computational model that manipulates symbols on an infinite tape according to a set of rules, providing a formal foundation for the concept of algorithm and computability.
All labels observed (4)
| Label | Occurrences |
|---|---|
| Turing machines | 13 |
| Turing machine canonical | 8 |
| universal Turing machine | 4 |
| Turing machine model | 1 |
Statements (60)
| Predicate | Object |
|---|---|
| instanceOf |
abstract computational model
ⓘ
automaton ⓘ formal system ⓘ mathematical model of computation ⓘ theoretical computer science concept ⓘ |
| coreConceptOf |
algorithm
ⓘ
decision problem ⓘ effective computability ⓘ halting problem ⓘ |
| describedInWork | On Computable Numbers with an Application to the Entscheidungsproblem ⓘ |
| fieldOfUse |
complexity theory
ⓘ
computability theory ⓘ mathematical logic ⓘ theoretical computer science ⓘ |
| hasComponent |
finite control
ⓘ
set of states ⓘ tape ⓘ tape head ⓘ transition function ⓘ |
| hasProperty |
can be encoded as a finite description
ⓘ
can be extended to nondeterministic variants ⓘ can be simulated by a universal Turing machine ⓘ can enter halting states ⓘ can simulate any algorithmically computable function ⓘ computes by successive configurations ⓘ configuration is determined by state tape contents and head position ⓘ deterministic in its basic form ⓘ discrete space model ⓘ discrete time model ⓘ has a designated start state ⓘ has a distinguished blank symbol ⓘ has a finite alphabet of tape symbols ⓘ is a basis for the Church–Turing thesis ⓘ is equivalent in power to lambda calculus ⓘ is equivalent in power to recursive functions ⓘ is equivalent in power to register machines ⓘ is used in proofs of incompleteness ⓘ is used in proofs of undecidability ⓘ is used in reductions between problems ⓘ is used to define Turing-computable functions ⓘ is used to define complexity classes ⓘ is used to define decidability ⓘ is used to define semi-decidability ⓘ is used to formalize algorithms ⓘ manipulates symbols ⓘ may have one or more halting states ⓘ stepwise operation ⓘ supports head movement left or right ⓘ supports read and write operations ⓘ uses infinite tape ⓘ |
| hasVariant |
alternating Turing machine
ⓘ
deterministic Turing machine ⓘ multi-tape Turing machine ⓘ multi-track Turing machine ⓘ nondeterministic Turing machine ⓘ oracle Turing machine ⓘ probabilistic Turing machine ⓘ universal Turing machine ⓘ |
| introducedIn | 1936 ⓘ |
| namedAfter | Alan Turing ⓘ |
Referenced by (26)
Full triples — surface form annotated when it differs from this entity's canonical label.
On Computable Numbers with an Application to the Entscheidungsproblem
→
mainSubject
→
Turing machine
ⓘ
subject surface form:
On Computable Numbers, with an Application to the Entscheidungsproblem
this entity surface form:
Turing machines
On Computable Numbers with an Application to the Entscheidungsproblem
→
introducesConcept
→
Turing machine
ⓘ
subject surface form:
On Computable Numbers, with an Application to the Entscheidungsproblem
On Computable Numbers with an Application to the Entscheidungsproblem
→
introducesConcept
→
Turing machine
ⓘ
subject surface form:
On Computable Numbers, with an Application to the Entscheidungsproblem
this entity surface form:
universal Turing machine
this entity surface form:
Turing machines
this entity surface form:
Turing machines
this entity surface form:
Turing machines
this entity surface form:
Turing machines
this entity surface form:
Turing machines
this entity surface form:
Turing machines
this entity surface form:
Turing machines
this entity surface form:
universal Turing machine
this entity surface form:
Turing machines
this entity surface form:
Turing machines
this entity surface form:
universal Turing machine
this entity surface form:
universal Turing machine
this entity surface form:
Turing machine model
subject surface form:
Neural Turing Machines
this entity surface form:
Turing machines
subject surface form:
Introduction to Automata Theory, Languages, and Computation
this entity surface form:
Turing machines
this entity surface form:
Turing machines
subject surface form:
MIP = NEXP