Linked from

The 53 pages that link to Turing machine, each with the reason it gives.

• Formal languageRelated: Turing machines recognize recursively enumerable languages, a broad class of formal languages.

• Alan TuringBroader topic: Turing introduced this model to define what a mechanical computation can do.

• AlgorithmRelated: It gives a formal framework for defining which step-by-step procedures can be computed.

• Finite-state machineCompared with: Its unbounded tape contrasts with the finite memory of a finite-state machine.

• Halting problemNarrower topic: The problem is defined over computations that can be represented by these machines.

• Church–Turing thesisBroader topic: This is the precise computational model named in the thesis.

• Computability theoryRelated: It provides a standard formal model for defining algorithmic computation.

• Mathematical logicRelated: It provides a precise model for defining effective procedures and undecidable problems.

• Alonzo ChurchRelated: Turing’s model independently matched the computational power of Church’s formal approach.

• Computer scienceBroader topic: It provides a precise model for defining computation and computability.

• Lambda calculusCompared with: Its independent model of computation helped establish lambda calculus as computationally equivalent in power.

• Computational complexity theoryRelated: It supplies a standard machine model for defining resource-bounded computation.

• P versus NP problemNarrower topic: Complexity classes are defined using formal models such as Turing machines.

• Decision problemRelated: Turing machines provide a standard mathematical model of effective procedures.

• EntscheidungsproblemRelated: Turing used machine behavior to show that no general validity-deciding algorithm can exist.

• Rice's theoremNarrower topic: The theorem is commonly formulated for programs modeled as Turing machines.

• Kolmogorov complexityNarrower topic: The choice of computational model underlies the programs whose lengths define complexity.

• Computable functionRelated: A function is computable when a Turing machine halts with its value for every valid input.

• Many-one reductionNarrower topic: Computability of the transforming function is commonly defined using this model.

• DecidabilityRelated: A Turing machine that halts on every input witnesses decidability.

• Partial functionRelated: A machine that halts only on some inputs defines a partial computable function.

• Universal Turing machineNarrower topic: A universal Turing machine is itself a Turing machine, equipped to interpret encoded machines.

• Cook–Levin theoremRelated: A machine's bounded computation supplies the configurations encoded by the formula.

• Pushdown automatonCompared with: Its tape is more flexible than a pushdown automaton’s restricted stack.

• Deterministic algorithmRelated: A deterministic Turing machine has one prescribed transition for each applicable state and symbol.

• Deterministic finite automatonCompared with: Its unbounded tape enables computation beyond finite-state memory.

• Finite automatonCompared with: Its unbounded memory allows computations finite automata cannot perform.

• Computational theory of mindBroader topic: It supplies a formal model for the computations some theories attribute to minds.

• History of computingNarrower topic: It separated the logic of computation from the material design of any particular machine.

• Undecidable problemNarrower topic: Undecidability is defined relative to what algorithms in a computational model can do.

• Polynomial timeRelated: Complexity theory commonly defines running time by counting its computation steps.

• Digital computerCompared with: It captures computability in theory rather than describing a practical digital computer.

• Analog computerCompared with: It formalizes discrete computation, unlike analog computers that calculate through physical magnitudes.

• Chomsky hierarchyRelated: Turing machines characterize the languages generated by unrestricted grammars.

• Stephen CookRelated: The theorem’s reduction encodes computations of nondeterministic Turing machines as formulas.

• Unary numeral systemRelated: Unary input makes elementary machine operations simple to specify, though often inefficient.

• Automata theoryBroader topic: Turing machines extend automata models to capture computability and undecidability.

• State machineCompared with: Its unbounded memory gives it computational power beyond finite-state machines.

• Nondeterministic Turing machineNarrower topic: Nondeterministic Turing machines extend this general model with multiple permitted moves.

• Oracle Turing machineNarrower topic: Oracle machines extend this model with a special membership-query operation.

• Simulation hypothesisBroader topic: It gives a precise model of what it means for a system to compute.

• Tower of HanoiRelated: Variants of the puzzle have been used to study the resources needed for computation.

• Computable setRelated: A halting Turing machine can decide membership for every input.

• Formal scienceBroader topic: It supplied a precise model for defining and analyzing computation.

• Theoretical computer scienceRelated: It provides a precise model for defining algorithms and computability.

• Computably enumerable setNarrower topic: Its computations provide a precise model for algorithms that enumerate sets.

• Computable numberRelated: A Turing machine formalizes the algorithm that produces each rational approximation.

• Theory of computationRelated: It provides a standard model for defining algorithms and computability.

• History of computer scienceBroader topic: It formalized computation in a model that could describe what machines can calculate.

• Linear speedup theoremNarrower topic: The theorem changes the machine model’s tape encoding and transition rules.