The Turing machine and computability
This page delivers no verdict; it presents claims and evidence with their sources. No theory in science is absolute. Method
For everyone
In 1936 Turing defined an abstract machine able to imitate any mechanical calculation, and with it proved that there are problems no algorithm can solve, the best known being whether a program will halt (the halting problem). This idea is the theoretical basis of today's computers.
For specialists
Turing showed that a universal machine can take the description of any other machine as input and simulate it. By a diagonal argument he proved the halting problem undecidable and answered Hilbert's Entscheidungsproblem in the negative. Church reached the same result independently with the λ-calculus. The Church–Turing thesis states that "effectively computable" coincides with Turing-computable; it is a thesis, not a theorem.
Claims
- There is no general algorithm deciding whether a program halts on every input.[1]
Evidence
Supporting
The diagonal argument shows that if such an algorithm existed, a program contradicting it could be constructed.[1]
Challenging
—
Positions
- Those questioning the strong (physical) form of the Church–Turing thesis
- Whether physical processes, for example quantum or relativistic systems, could compute what Turing machines cannot is an open question.[2]
Connections
Influenced by
Related
This topic is a stop on these journeys
Sources
- Article (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society s2-42(1), 230–265DOI 10.1112/plms/s2-42.1.230archive
- EncyclopediaThe Church–Turing Thesis. Stanford Encyclopedia of Philosophyplato.stanford.eduarchive
Search the literature
Look for scholarly work on this topic in other indexes:
Cite this page
Athena contributors. (2026). The Turing machine and computability. Athena: The tree of human knowledge. Retrieved November 1, 2026, from https://latifkedi.github.io/athena/en/d/turing/
@misc{athena_turing,
title = {The Turing machine and computability},
author = {{Athena contributors}},
year = {2026},
howpublished = {\url{https://latifkedi.github.io/athena/en/d/turing/}},
note = {Athena: The tree of human knowledge. Accessed: 2026-11-01}
}Added: September 27, 2026 · Last changed: September 28, 2026 · Page history