Turing’s undecidability theorem
logic
Also known as: Church-Turing theorem
Learn about this topic in these articles:
foundations of mathematics
- In foundations of mathematics: Recursive definitions
The Church-Turing theorem of undecidability, combined with the related result of the Polish-born American mathematician Alfred Tarski (1902–83) on undecidability of truth, eliminated the possibility of a purely mechanical device replacing mathematicians.
Read More
metalogic
- In metalogic: The undecidability theorem and reduction classes
Turing’s method of proving that this class of problems is undecidable is particularly suggestive. Once the concept of mechanical procedure was crystallized, it was relatively easy to find absolutely unsolvable problems—e.g., the halting problem, which asks for each Turing machine the question of whether it will…
Read More