Church-Turing thesis
Computation's fundamental limit
The Church-Turing thesis is the proposition that any computation performable by an algorithm can be performed by a Turing machine—a theoretical device that manipulates symbols on a tape according to rules.
Named for mathematicians Alonzo Church and Alan Turing, it defines the boundaries of what is computable in principle.
The thesis cannot be proven mathematically but is universally accepted in computer science as capturing the intuitive notion of effective calculation.
- recursiveDefined in terms of itself
- algorithmFinite problem-solving procedure
- functionPurpose or duty
- automataSelf-moving mechanical devices
- Gödel numberingMapping syntax to integers
proof · tape · oracle · equivalence · finite · symbolic logic · computability · universal · limits · mechanical · symbols · logic · completeness · diagonalization · reduction · decidable · intuitionism · logical paradoxes
- Computabilitycomputability, decidability, completeness
- logicpremise, premises, conclusion, conclusions, inference