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.
Aliases (2)
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 (8)
| Subject (surface form when different) | Predicate |
|---|---|
|
On Computable Numbers, with an Application to the Entscheidungsproblem
→
On Computable Numbers, with an Application to the Entscheidungsproblem ("universal Turing machine") → |
introducesConcept |
|
Chomsky hierarchy
→
|
correspondsToAutomatonModel |
|
Alan Turing
→
|
knownFor |
|
On Computable Numbers, with an Application to the Entscheidungsproblem
("Turing machines")
→
|
mainSubject |
|
Entscheidungsproblem
("Turing machines")
→
|
provedUndecidableUsing |
|
Gödel, Escher, Bach
("Turing machines")
→
|
subject |
|
Introduction to the Theory of Computation
("Turing machines")
→
|
topic |