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

Why the Thesis Cannot Be Proven

Understanding that the thesis connects informal intuition to formal definition, not mathematical statements to each other.

Why the Thesis Cannot Be Proven

You'll learn why the Church-Turing Thesis stands apart from typical mathematical theorems and cannot be formally proven.

The Church-Turing Thesis states that anything we would intuitively call an "algorithm" or "effective procedure" can be computed by a Turing Machine (or equivalently, by lambda calculus or recursive functions). This sounds like a mathematical statement, so why can't we prove it?

The Nature of the Thesis

Here's the key insight: the Church-Turing Thesis connects two different kinds of things:

  • Informal, intuitive concept: "algorithm" or "effective procedure" (something a human could carry out mechanically with paper and pencil)
  • Formal mathematical definition: Turing Machine (precisely defined mathematical object)

Mathematical proofs work by connecting one formal statement to another using logical rules. But you cannot prove a connection between an informal idea and a formal definition. The informal side lacks the mathematical precision needed for proof.

An Analogy

Think of it like trying to prove "all beautiful paintings can be captured by photographs." What exactly is "beautiful"? Until you formally define beauty with mathematical precision, you can't prove anything about it. The Church-Turing Thesis faces the same issue: "effective procedure" is an intuitive notion, not a formal mathematical object.

Why We Accept It

Instead of proof, we have overwhelming evidence: every model of computation anyone has proposed (Turing machines, lambda calculus, recursive functions, modern programming languages) turns out to be equivalent in power. After decades of attempts, no one has found a counterexample or a more powerful model.

Key Takeaway: The Church-Turing Thesis cannot be proven because it bridges informal human intuition about computation with formal mathematical definitions—and you cannot mathematically prove relationships between informal concepts and formal ones.