Course contentsShow
← Computer Science
Lesson 1865 of 2,87242. Turing Machines and ComputabilityFree lesson

Statement of the Church-Turing Thesis

The thesis: every effectively computable function is computable by a Turing machine (or equivalent model).

Statement of the Church-Turing Thesis

What You'll Learn

You'll learn the bold claim that unifies all models of computation and defines what it means for something to be "computable" at all.

The Central Claim

After exploring Turing machines, lambda calculus, and recursive functions—three completely different mathematical models invented around the same time—computer scientists noticed something remarkable: they all compute exactly the same set of functions. This led to a profound hypothesis.

The Church-Turing Thesis states:

Every function that can be effectively computed by following a mechanical, step-by-step procedure (an algorithm) can be computed by a Turing machine.

Put differently: if you can describe a clear, finite set of instructions that a human could follow mechanically to solve a problem, then a Turing machine can solve it too.

Why It's a "Thesis," Not a Theorem

This isn't something we can prove mathematically because "effectively computable" isn't a formal mathematical term—it's an intuitive notion about what humans can calculate. We can't prove intuition equals formalism.

However, the thesis is universally accepted because:

  • Every formal model anyone has invented (Turing machines, lambda calculus, recursive functions, modern programming languages) computes the same class of functions
  • No one has found a convincing counterexample in nearly 90 years
  • It provides the foundation for defining what problems computers can and cannot solve

The Practical Implication

The Church-Turing Thesis tells us that Turing machines aren't just one model among many—they capture the limits of computation itself. If something can't be done on a Turing machine, it can't be done algorithmically at all.

Key Takeaway: The Church-Turing Thesis equates intuitive "algorithmic computation" with "Turing machine computation," establishing Turing machines as the universal standard for what is computable.