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

Equivalence of Computational Models

How Turing machines, lambda calculus, and recursive functions compute exactly the same class of functions.

Equivalence of Computational Models

What You'll Learn

You'll discover why Turing machines, lambda calculus, and recursive functions—despite looking completely different—can compute exactly the same set of functions.

The Core Idea

Imagine three different languages that can express exactly the same thoughts. One might be verbose, another symbolic, and a third minimalist—but if you can say anything in one, you can translate it perfectly into the others.

That's what happens with our three models of computation:

  • Turing machines use a tape, read/write head, and state transitions
  • Lambda calculus uses function definitions and applications with symbolic expressions
  • Recursive functions build complex functions from simple primitives like zero, successor, and composition

Each model was developed independently to formalize the notion of "algorithm" or "effective computation." Remarkably, researchers discovered that any function computable in one model can be computed in all the others. If you can write an algorithm as a Turing machine, you can write an equivalent lambda calculus expression, and vice versa.

This isn't a coincidence—it reveals something fundamental about computation itself. The class of functions all three can compute is called the computable functions (or recursive functions), and this equivalence strongly suggests we've captured the true essence of what it means to "compute."

This equivalence is known as the Church-Turing thesis: these different formalisms all define the same boundary between what can and cannot be algorithmically computed.

Why It Matters

This equivalence means you can choose whichever model is most convenient for proving something about computability. It also gives us confidence that we've found the "right" definition of algorithm—multiple independent approaches converged on the same answer.

Key Takeaway: Turing machines, lambda calculus, and recursive functions are provably equivalent—they compute exactly the same class of functions, suggesting we've captured the fundamental nature of computation itself.