##  [Church–Turing Thesis](/church-turing-thesis-0) 

 Definition

An informal foundational claim that any function which can be computed by a finite, mechanical procedure (an effective algorithm) can be computed by a Turing machine; it identifies Turing-computability with the intuitive notion of algorithmic computability.

 

 

 

 

 

 





## Principle

Principle

That a single formal model (Turing machines, equivalently lambda calculus, recursive functions, etc.) captures the informal concept of what it means to compute effectively.

 

 

 

 

 





## Demonstration

Demonstration

Concrete domain example: any algorithm expressed in a modern programming language can be translated into an equivalent Turing-machine procedure that, given an encoding of inputs, reproduces the same output behavior; equivalence is shown by constructing a simulator for the programming-language semantics on a universal Turing machine.

 

 

 

 

## Misapplication

Misapplication

Claiming the Church–Turing thesis is a proved mathematical theorem about all physical processes, or using it to assert bounds on time or space (complexity) rather than on computability; or asserting it rules out any form of hypercomputation without empirical justification.

 

 

 

 

 





## Consequence

Consequence

Provides a widely accepted baseline for computability theory and for classifying problems as decidable or undecidable; justifies using Turing machines (or equivalent models) as canonical for discussing what is computable in principle.

 

 

 

 

## Reversal

Reversal

The inverted claim would posit the existence of an effective procedure intuitively describable that no Turing machine can implement — i.e., a feasible algorithm outside Turing-computability.

 

 

 

 

 





## Boundary

Boundary

A thesis, not a formal theorem: it concerns what counts as an effective algorithm and does not by itself address resource bounds (time/space), probabilistic or approximate computation, or empirical physical realizability; extensions that assert physical limits (physical Church–Turing theses) are separate and contingent.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Tension between 'computable in principle' (theoretical equivalence to Turing machines) and 'computable in practice' (resource-bounded, physical, or approximate computation), and between a descriptive thesis and a normative or empirical claim about physical systems.

 

 

 

 

 





## Synthesis

Synthesis

The Church–Turing thesis states that the informal notion of an effective algorithm is captured by Turing computability: it organizes computability theory by equating intuitive algorithmic procedures with the formal Turing-machine model, while leaving open questions about resources and physical realization.