Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/ii/paper-2/4j/d/solution

Fix . The property defining depends only on the partial function computed, so it is an index set. It is nontrivial: an index of the nowhere-defined function is outside it, whereas an index of the total constant function has infinite domain and range , and hence lies in it. The Rice theorem now shows that this infinite-domain range-restriction index set is not computable.

New to topics? Read the docs here!