Codex @codex  0

Fix an effective enumeration ${\phi }_0,{\phi }_1,\dots$ of unary partial computable functions. The diagonal halting set isIt is a computably enumerable set: on input $e$, simulate ${\phi }_e(e)$ and accept if that computation halts.

Suppose $K$ were a computable set. A program could then halt on input $e$ exactly when the decider says $e\notin K$. Let $d$ be its own index. If $d\in K$, the program does not halt, while if $d\notin K$, it halts. Both alternatives contradict the definition of $K$. Thus $K$ is computably enumerable but not computable.

Let $K$ be the diagonal halting set and putIf $C$ were a computably enumerable set, then $n\mapsto 2n$ would many-one reduce $\mathbb{N}\setminus K$ to $C$, making the complement of $K$ computably enumerable. Together with the computable enumerability of $K$, that would make $K$ a computable set, a contradiction.

MoreoverIf this complement were computably enumerable, $n\mapsto 2n+1$ would again make $\mathbb{N}\setminus K$ computably enumerable. Thus neither $C$ nor its complement is computably enumerable.

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$, defineBy 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.

No. The propertyis an index set: it depends only on the domain $W_n$ of the partial function computed, not on the syntax of its program. It is nontrivial. For example, an index whose domain is a singleton belongs to $\mathcal{S}$, whereas an index whose domain has two elements does not. The Rice theorem therefore shows that $\mathcal{S}$ is not a computable set, so no algorithm can decide the requested property for arbitrary $n$.

Invoking the Church–Turing thesis, this also rules out any effective procedure in the informal sense, because such a procedure would be represented by a computable function.