A programmer writes a function f that is computable and she has proven it halts on every possible input. What is the correct classification of f?
Af is a total recursive function, because it is computable and halts for all inputs
Bf is partial recursive but not total, because all computable functions may fail to terminate on some inputs
Cf is primitive recursive but not total recursive, because total recursive functions require additional proof techniques
Df cannot be classified without knowing whether it uses the µ-operator
A total recursive function is exactly a function computed by some Turing machine (or equivalent formalism) that halts and returns a value on every input. 'Total' means 'halts for all inputs,' and 'recursive' means 'computable.' The programmer's function satisfies both conditions. Option B is the classic misconception: partial recursive functions are those that *may* fail to terminate on some inputs, not all computable functions. A computable function that provably terminates everywhere is by definition total recursive.
Question 2 Multiple Choice
A theorem states that the set of total recursive functions is not recursively enumerable. What does this imply for a hypothetical program TOTAL(f) that claims to decide whether any given program f halts on every input?
ATOTAL(f) would need to run f on all inputs before deciding, but could still halt in principle for finite input domains
BTOTAL(f) cannot exist as a computable algorithm — deciding totality is undecidable
CTOTAL(f) exists but requires exponential time to terminate
DTOTAL(f) exists for all primitive recursive programs but fails only for µ-recursive programs
If TOTAL(f) existed as a total recursive function, it would semi-decide which programs halt on all inputs. But totality is undecidable by reduction from the halting problem: to ask whether M halts on w, build a new function g that simulates M on w on any input; g is total iff M halts on w. Since halting is undecidable, totality is undecidable. The non-enumerability result is even stronger: you cannot even semi-decide totality — there is no algorithm that accepts exactly the total programs.
Question 3 True / False
Nearly every partial recursive function can be extended to a total recursive function by defining its output to be 0 on inputs where it would otherwise diverge.
TTrue
FFalse
Answer: False
This is a common misconception. While you can mathematically define a total function that agrees with f on halting inputs and outputs 0 elsewhere, this extended function is not necessarily computable. Computing it requires knowing which inputs cause f to diverge — but recognizing the domain of a partial recursive function is not in general computable (it is equivalent to the halting problem). So although a total extension exists as a mathematical object (a set of ordered pairs), there need not be any algorithm that computes it. You cannot freely convert a partial computable function into a total computable one.
Question 4 True / False
A function that is defined (returns a value) for most natural number input is expected to be computable by some Turing machine.
TTrue
FFalse
Answer: False
Totality and computability are independent properties. The total computable functions are a strict subset of all total functions. There exist functions provably defined on every input that are not computable by any Turing machine — the Busy Beaver function Σ(n) is a classic example: it is defined for every n (it counts something specific), but it grows faster than any computable function and cannot be computed algorithmically. The gap between 'all total functions' and 'total computable functions' is a central object of study in computability theory.
Question 5 Short Answer
Explain why partiality is unavoidable in any sufficiently powerful computational model: why can't we simply restrict to total programs while keeping the same expressive power?
Think about your answer, then reveal below.
Model answer: Any computational model powerful enough to simulate arbitrary programs — including itself — will necessarily contain programs that loop forever on some inputs. If you try to restrict to only total programs while keeping full expressive power (the ability to compute all computable functions), you face a diagonalization argument: given any enumeration of supposedly total programs, you can construct a function that differs from each one on some input — this new function is total (defined everywhere) but cannot be in your enumeration, so your enumeration was incomplete. More concretely, the set of total recursive functions is not recursively enumerable, meaning no algorithm can enumerate all of them. Any programming language that guarantees termination — like a proof assistant's type-checked term language — necessarily sacrifices the ability to compute some computable functions.
This connects the partial/total distinction to the fundamental limits of formalism. Dependently-typed proof assistants like Coq and Agda guarantee termination through structural recursion but cannot compute all computable functions. General-purpose languages (Python, C) admit all computable functions but inevitably include non-terminating programs. This is not a design failure — it is a mathematical necessity that follows from diagonalization.