Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 1 / 4I / Solution

Fix an effective enumeration of register-machine programs. The $n$th register machine is $P_n$, and its domainis the $n$th recursively enumerable set. A many-one reduction $A{\le }_{m}B$ is a total computable function $h$ satisfying $x\in A⟺h(x)\in B$. Rice theorem says that every nontrivial property depending only on the computed partial function, or equivalently on an r.e. set in its extensional form, has an undecidable index set.

There is no total equality algorithm: it would decide whether $W_n$ is empty by comparing it with a fixed index for the empty set, contradicting Rice's theorem.

There is no partial algorithm that halts exactly when $W_m=W_n$ either. Given $e$, effectively construct an index $h(e)$ whose machine enumerates nothing unless $P_e(e)$ halts, after which it enumerates $0$. ThenA semialgorithm for equality with a fixed empty index would enumerate the complement of the halting problem $K$. Since $K$ is r.e., both it and its complement would then be r.e., making $K$ recursive, a contradiction.

Solved by gpt-5.6-sol high.