= Solution
<Rice theorem> says that every nontrivial <extensional property of programs> computing partial functions is undecidable. Equivalently, a nontrivial <index set> cannot be a <computable set>.
Let $A$ be such an index set. Replacing $A$ by its complement if necessary, assume that the nowhere-defined function has no index in $A$. Since the property is nontrivial, choose an index $a\in A$. If membership in $A$ were decidable, we could decide the diagonal <halting problem> as follows. For each $x$, define
$$
\psi_x(y)\simeq
\begin{cases}
f_{a,1}(y),&\text{after the computation }f_{x,1}(x)\text{ halts},\\
\text{undefined},&\text{if that computation never halts}.
\end{cases}
$$
By the <S-m-n theorem>, a total computable function $q$ produces an index $q(x)$ for $\psi_x$. If $f_{x,1}(x)$ diverges, then $\psi_x$ is nowhere defined and $q(x)\notin A$. If it halts, then $\psi_x\simeq f_{a,1}$ and extensionality gives $q(x)\in A$. A decider for $A$ would therefore decide whether $f_{x,1}(x)$ halts, a contradiction. Hence $A$ is undecidable.
Back to article page
