Questions: General Recursive Functions and the μ-Operator

Question 1

A function f(n) is defined as f(n) = μx[g(x, n) = 0]. Which best describes f?

• A. f is always total, because the μ-operator is guaranteed to find a solution
• B. f is total only when g is primitive recursive
• C. f may be undefined for some n, if no x satisfies g(x, n) = 0 or g diverges on a smaller input
• D. f computes strictly more functions than a Turing machine, since unbounded search is more powerful

Answer: (C)

The μ-operator finds the *least* x satisfying the condition, but if no such x exists — or if g is undefined for some intermediate input — the search runs forever and f is undefined on that n. This partiality is the defining feature that distinguishes general recursive functions from primitive recursive ones. Option D is wrong: general recursive functions compute exactly the same class as Turing machines, not more.

Question 2

What is the most compelling mathematical evidence for the Church-Turing thesis?

• A. Church personally verified that lambda calculus and Turing machines always produce identical results on test inputs
• B. Three entirely independent formalizations — recursive functions, lambda calculus, and Turing machines — each developed from different starting points and all define exactly the same class of computable functions
• C. No counterexample to the thesis has been discovered using any physical hardware
• D. Primitive recursive functions are a proper subset of all three frameworks, confirming a shared foundation

Answer: (B)

The compelling argument is the remarkable convergence: Gödel (recursive functions), Church (lambda calculus), and Turing (machines) each approached computability from entirely different mathematical starting points and independently arrived at the same class of functions. This robustness across three uncoordinated formalizations is strong evidence — though not proof — that the class captures something intrinsic about the nature of effective computation.

Question 3

The fact that partial recursive functions can be undefined on some inputs is a deficiency of the formalism — a complete theory of computation should cover most possible inputs.

• T. True
• F. False

Answer: False

Partiality is not a defect but a fundamental and necessary feature. The halting problem proves that no total computable function can decide whether an arbitrary program terminates. Any model that restricts to total functions is provably incomplete — primitive recursive functions already miss the Ackermann function. The μ-operator deliberately introduces partiality to match the natural limit of computability: some computations run forever, and the theory must represent this honestly.

Question 4

Nearly every total recursive function — one that terminates on most inputs — is also primitive recursive.

• T. True
• F. False

Answer: False

The Ackermann function is the canonical counterexample. It is total (defined and terminating for all natural number inputs) and general recursive (expressible with the μ-operator), but it grows faster than any primitive recursive function and provably cannot be expressed using only composition and primitive recursion. The total recursive functions strictly include the primitive recursive ones. Moreover, deciding whether a given general recursive function is total is itself undecidable.

Question 5

Why can we enumerate all partial recursive functions but not algorithmically identify which ones among them are total?

Model answer: We can enumerate all partial recursive functions by systematically listing all finite programs or recursive definitions — there are countably many. But deciding whether any given program halts on all inputs is the halting problem, which is undecidable. We have no algorithm to filter the enumeration to keep only the total ones. The 'total recursive functions' is a semantically-defined class (those general recursive functions that happen to always terminate), and membership is not algorithmically checkable.

This follows from Rice's theorem: any non-trivial semantic property of programs (including 'is total') is undecidable. You can generate an infinite list of all recursive programs, but you cannot build a halting filter. The distinction between the syntactically-defined class of all partial recursive programs and the semantically-defined subclass of total ones is a fundamental asymmetry in computability theory.