Church-Turing Thesis

Origin. Church (1936), Turing (1936), Kleene. Identifies the informal notion of effective calculability with a formal model of computation. A thesis, not a theorem: it links intuition to mathematics.

Models. Any function computable by an algorithm is computable by a Turing machine (equivalently λ-definable, general recursive). The convergence of many independently designed models is the central evidence.

Formalism.

Statement: Effectively calculable = Turing computable = partial recursive = λ-definable. The informal class equals the formal class.

Equivalent models: Turing machines. λ-calculus. General recursive functions. Register/counter machines. Post canonical systems. Cellular automata. All define the same function class.

Evidence: Every proposed model of effective computation coincides. Robust under variation (tapes, symbols, nondeterminism → same class). No counterexample in ninety years.

Physical Church-Turing thesis: Any physically realizable computation is Turing computable. Stronger, empirical claim about nature.

Extended (feasibility) thesis: Efficiently computable = polynomial time (P). Challenged by randomized and quantum models.

Turing completeness: A system that can simulate a universal Turing machine. Sufficient for full computational power.

Symbols.

Symbol	Unicode	Name	Meaning
TM	—	Turing machine	Standard model
λ	U+03BB	Lambda	λ-definability
CT	—	Church-Turing	The thesis
P	—	Polynomial time	Feasibility class

Metatheory. Not provable: one side is informal. Refutable in principle by a convincing effective procedure computing a non-recursive function. Underlies every undecidability argument (an informal algorithm suffices to show a set r.e.).

Applies to. Foundations of computation. Undecidability proofs. Complexity theory (extended form). Philosophy of mind and computation.

Limitations. Cannot be proved. Physical and feasibility versions are empirical and contested. Says nothing about resource bounds in the basic form.