A mathematician defines function f: ℕ → ℕ that always produces a value and is defined for every natural number. She concludes: 'Since f always terminates and is total, it must be primitive recursive.' Is she correct?
AYes — every total function on the natural numbers is primitive recursive by definition
BYes — termination guarantees primitive recursiveness, since non-terminating functions are the only ones outside the class
CNo — the Ackermann function is total and always terminates but grows faster than any primitive recursive function, placing it strictly outside the class
DNo — primitive recursive functions must also be monotone increasing, which may not hold for f
Totality is necessary but not sufficient for primitive recursiveness. The Ackermann function A(m, n) is total — it terminates and returns a value for every pair of natural numbers — yet it is not primitive recursive. It grows faster than any primitive recursive function, which means no fixed primitive recursion scheme can define it. The class of primitive recursive functions is a strict subset of total computable functions. Option A is a common misconception; option D is simply false.
Question 2 Multiple Choice
Why can't the primitive recursion operation define the Ackermann function, even though the Ackermann function is clearly computable?
AThe Ackermann function is undefined for some inputs, making it non-total and thus outside the class
BPrimitive recursive functions cannot use more than two arguments, but Ackermann requires three
CPrimitive recursion only decreases a single argument in each recursive call, but the Ackermann function uses nested recursion of unbounded depth that escapes any fixed recursion scheme
DThe Ackermann function requires integer division, which is not primitive recursive
The limitation of primitive recursion is structural: each application of the scheme decreases one fixed argument toward 0, keeping the recursion depth bounded in advance. The Ackermann function's computation involves A(m, ·) being defined in terms of A(m−1, ·) applied a variable number of times, creating nested recursion whose depth grows with the inputs — no fixed primitive recursion scheme can match this. Options A and B are factually false. Option D is wrong; bounded division is primitive recursive.
Question 3 True / False
All primitive recursive functions are total — they return a value for every natural number input and never fail to terminate.
TTrue
FFalse
Answer: True
Totality is a defining property of primitive recursive functions. The base functions (zero, successor, projection) are clearly total. Composition of total functions is total. The primitive recursion scheme always terminates because the first argument strictly decreases toward 0 in each step — this is exactly a bounded loop. Because both operations preserve totality, every function built this way is total. This distinguishes primitive recursive functions from partial recursive functions, which may be undefined on some inputs.
Question 4 True / False
The Ackermann function lies outside the class of primitive recursive functions because it is not computable — no Turing machine can compute it.
TTrue
FFalse
Answer: False
This is false. The Ackermann function is fully computable — a straightforward Turing machine or recursive program can compute it (just run the recursive definition). It lies outside the primitive recursive class not because it is uncomputable, but because it grows faster than any primitive recursive function. The primitive recursive class is a strict subset of the computable functions; there exist total computable functions (like Ackermann) that are not primitive recursive. Non-computability is a separate, stronger condition.
Question 5 Short Answer
Why does the class of primitive recursive functions fail to capture all computable functions, and what operation must be added to close the gap?
Think about your answer, then reveal below.
Model answer: Primitive recursion only allows bounded loops — the recursion depth is determined in advance by the decreasing argument. This limits how fast the output can grow. The Ackermann function, requiring nested recursion of unbounded depth, outgrows every primitive recursive function. To capture all computable functions — including partial ones — we add the μ-operator (unbounded minimization): μy[f(x, y) = 0] searches for the smallest y satisfying a condition, with no prior bound on how far it must search. This may fail to terminate (making the result partial), but it gives us general recursive functions, which are exactly the Turing-computable functions.
The μ-operator is what lifts primitive recursive functions to general (partial) recursive functions. Kleene's normal form theorem shows that any partial recursive function can be expressed as primitive recursive functions plus one application of μ. The cost is losing the totality guarantee — μ may search forever — which is why partial recursive functions can be undefined on some inputs.