Solution

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

A many-one reduction is a total computable function with . If is recursively enumerable, compute and run a semidecision procedure for on that value. It halts exactly when , so is recursively enumerable. Totality of is essential to this argument.

New to topics? Read the docs here!