Alternative Models: Recursive Functions
What you'll learn: You'll discover how mathematicians define computability using pure functions and composition, offering a third perspective alongside Turing machines and lambda calculus.
The Mathematical Approach to Computation
While Turing gave us machines and Church gave us lambda calculus, mathematicians Stephen Kleene and Kurt Gödel asked: "Can we define computability using only basic arithmetic functions and composition rules?"
Recursive functions (also called general recursive functions or μ-recursive functions) build complex computations from the simplest possible mathematical building blocks:
Starting with Basic Functions
- Zero function: Always returns 0
- Successor function: Adds 1 to a number
- Projection functions: Select one input from many (like picking the 2nd argument)
Building Up with Operations
From these tiny pieces, you create sophisticated functions through:
- Composition: Chain functions together (output of one becomes input of another)
- Primitive recursion: Define functions using "previous values" (like factorial: n! = n × (n-1)!)
- Minimization (the μ operator): Find the smallest number that makes a function equal zero
Why This Matters
Think of it like LEGO blocks: you start with three basic shapes, then snap them together using fixed rules. Surprisingly, you can build anything computable this way—the same set of problems solvable by Turing machines or lambda calculus!
This mathematical purity makes recursive functions perfect for theoretical proofs about what's computable. It strips away tape, machines, and variables, leaving only the essence: functions calling functions, numbers transforming numbers.
Key Takeaway: Recursive functions prove that computability can be defined purely through mathematical function composition, starting from just three primitive operations—another equivalent model showing computation's mathematical foundation.