Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/ii/paper-2/4i/b/iii/solution

Suppose for a partial computable function . Since , fix . Decode each input as a pair . Using the truncated computation function, define
This is a total computable function, and every output lies in . Conversely, if , choosing at least the halting time gives an input with . Thus , proving (iii)(iv).

New to topics? Read the docs here!