= Solution
Fix an effective enumeration of register-machine programs. The $n$th register machine is $P_n$, and its domain
$$
W_n=\{x:P_n\text{ halts on input }x\}
$$
is the $n$th <recursively enumerable set>. A <many-one reduction> $A\leq_mB$ is a total computable function $h$ satisfying $x\in A\iff 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$. Then
$$
W_{h(e)}=\varnothing\iff e\notin K.
$$
A 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.
Back to article page
