Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 2 / 4J (Automata and Formal Languages)

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.

For the fixed effective enumeration of unary partial computable functions, the infinite-domain index set is

The Rice theorem states that every nontrivial index set of partial computable functions is not computable.

Fix $x_0\in X$. The property defining ${\mathbf{Inf}}_X$ depends only on the partial function computed, so it is an index set. It is nontrivial: an index of the nowhere-defined function is outside it, whereas an index of the total constant function $n\mapsto x_0$ has infinite domain and range $\{x_0\}\subseteq X$, and hence lies in it. The Rice theorem now shows that this infinite-domain range-restriction index set is not computable.