Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2017/ii/paper-3/11h/b/solution

The S-m-n theorem says that parameters can be compiled effectively into program indices: for a standard effective numbering, there is a total computable function with for partial computable functions of arguments.
Write , a recursively enumerable halting problem. If is recursively enumerable, make a program with parameter which ignores its input and runs a semidecision procedure for , halting when that procedure halts. By the S-m-n theorem its index is total computable and . Conversely, implies that is recursively enumerable by the previous construction. Thus .

New to topics? Read the docs here!