Linked from

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

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

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

• 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.

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

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

• 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.

• 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.

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

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

• Turing's proofNarrower topic: Turing formalizes algorithms as machines whose halting behavior can be analyzed.