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.