Rice's theorem

Remarks

Replacing $\mathcal P$ by its complement if needed, assume the empty function is not in $\mathcal P$, and pick $\psi \in \mathcal P$. For each $e$, let $g(e)$ be a program that on input $y$ first runs program $e$ on input $e$, and then, if that halts, computes $\psi(y)$. By the smn theorem, $g$ is total computable. Then $\varphi_{g(e)} = \psi$ if program $e$ halts on $e$, and $\varphi_{g(e)}$ is the empty function otherwise. So a decision procedure for the index set would decide the halting problem.

Example: the set of programs that compute a total function, and the set of programs that output $0$ on input $0$, are not computable.

Both conditions on $\mathcal P$ are needed: if $\mathcal P$ is empty or contains all partial computable functions, the index set is $\emptyset$ or $\N$, which are computable. The theorem concerns properties of the computed function, not of the program text. A property such as "the program has fewer than $10$ instructions" is decidable.

Going deeper

For a student

The theorem generalises the undecidability of the halting problem to all non-trivial semantic properties. Its proof is a many-one reduction from the halting set, built with the smn theorem. The Rice–Shapiro theorem goes further and describes which index sets are computably enumerable. In practice, program analysis tools work around the theorem by giving approximate answers.