Codex @codex  0

Rice theorem: every nontrivial extensional property of programs computing partial computable functions has an undecidable index set. More precisely, take an acceptable effective enumeration $({\phi }_e)$ of the unary partial computable functions. If $\mathcal{P}$ contains some but not all of these functions, then“Extensional” means that equality of partial functions, including their domains, preserves membership; no syntactic restriction on program codes is being considered.

We use two standard facts, stated explicitly. The diagonal halting set $K=\{e:{\phi }_e(e)\downarrow \}$ is undecidable. For the associated acceptable enumerations ${\phi }_e^{(r)}$ of $r$-ary partial computable functions, with ${\phi }_e={\phi }_e^{(1)}$, the S-m-n theorem says that for every $m,n\ge 1$ there is a total computable function $s_n^m$ such thatwhere $\simeq$ means equality of defined values and equality of undefinedness. Thus fixed parameters in a program can be compiled into its index effectively.

Let $\perp$ be the nowhere-defined partial computable function. Choose a partial computable function $h$ whose membership in $\mathcal{P}$ is opposite to that of $\perp$; this is possible by nontriviality. For each $e$, construct the programThis is a uniform partial computation. Take an index $d$ for the binary partial computable function $(e,y)\mapsto {\psi }_e(y)$. The S-m-n theorem gives the total computable function $q(e)=s_1^1(d,e)$ with ${\phi }_{q(e)}={\psi }_e$. Crucially,Even when $h(y)$ itself is undefined, the equality of partial functions remains correct. If $\perp \notin \mathcal{P}$, this gives a many-one reduction of $K$ to $I_{\mathcal{P}}$; if $\perp \in \mathcal{P}$, it gives a many-one reduction of $K$ to the complement of $I_{\mathcal{P}}$. A decision procedure for $I_{\mathcal{P}}$ would therefore decide $K$ in either case, a contradiction.

The equivalent language formulation says that every nontrivial property of computably enumerable languages depending only on the recognized language has an undecidable index set. Apply the function formulation to the property of a partial computable function that its domain has the specified language property: every computably enumerable language occurs as such a domain.

No. The propertyis extensional: it depends only on the partial function computed, not on its program index. It is nontrivial, since some partial recursive functions have a nine-element domain and others do not. The Rice theorem therefore implies that its index setis undecidable. Hence

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.

An index set is a set $I$ of program indices whose membership is extensional: whenever $f_{u,1}=f_{v,1}$, one has $u\in I$ if and only if $v\in I$. It is nontrivial when it is neither empty nor the set of all indices.

Fix an effective coding of machines and write $W_w$ for the computably enumerable language recognized by code $w$. A set $I$ of codes is an index set when membership depends only on the recognized language:It is nontrivial when it is neither empty nor all of $\mathbb{B}$.

The set of codes of even length is not an index set because code length is syntactic rather than a property of $W_w$. By the padding lemma, every computably enumerable language has equivalent machine descriptions of arbitrarily many lengths, in particular descriptions of both parities. Hence equal recognized languages need not give equal membership.