Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2020/ii/paper-1/12f/b/solution
Past exam of the mathematics course of the University of Cambridge 2020 ii Paper 1 12F b Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-29
The partial recursive functions form the smallest class containing the zero function, successor function, and projection functions and closed under composition, primitive recursion, and unbounded minimization.
Fix a register machine with inputs. By the permitted result, its complete configuration after steps,is a recursive function of the inputs and time. The predicate saying that this configuration is halted is therefore recursive. Its halting time is the partial recursive functionwhere unbounded minimization is undefined when no halting time exists. Extracting the output register from a configuration is recursive, sois partial recursive. Hence every partial computable function is partial recursive.
New to topics? Read the docs here!