Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 3 / 12H / a / Solution

Fix an acceptable effective enumeration $f_{e,n}$ of the $n$-ary partial computable functions. The S-m-n theorem states that for every $m,n\ge 1$ there is a total computable function $s_n^m$ such thatwhere $\simeq$ means that both sides have the same value when defined and are otherwise both undefined.

The recursion theorem states that every total computable transformation $h$ of program indices has a semantic fixed point: there is an $e$ such that