= Solution
A <partial computable function> is the <function> computed by a finite program, with an undefined value when its computation never terminates. A <total computable function> terminates on every input. Fix an effective enumeration $(\varphi_e)_{e\in\omega}$ of the <partial computable functions>, with a <universal partial computable function> $U(e,x)=\varphi_e(x)$. Composition, <primitive recursion> and <unbounded minimization> give a machine-independent description of this class. <Unbounded minimization> is allowed to diverge. The <S-m-n theorem> permits parameters in a program to be specialized effectively: an algorithm described uniformly in $e$ has an index obtained computably from $e$.
The <halting set> $K=\{e:\varphi_e(e)\text{ halts}\}$ is <computably enumerable>: simulate all computations in parallel and enumerate each index whose diagonal computation terminates. It is not a <computable set>. Otherwise the program which terminates exactly when the proposed decision procedure says its own diagonal computation does not terminate gives a contradiction. There is also no effective enumeration consisting exactly of all <total computable functions>: from such an enumeration $(f_n)$ the <total computable function> $g(n)=f_n(n)+1$ differs from every listed <function>. Thus the effective enumeration of partial programs cannot be replaced by a decidable catalogue of total ones.
For the <Rice theorem>, let $C$ be a nontrivial property of <partial computable functions>, depending on the computed <function> rather than the program text. First suppose the nowhere-defined <function> is not in $C$, and choose a program computing some $g\in C$. Uniformly in $e$, define a program which, on input $x$, first waits for $\varphi_e(e)$ to terminate and then runs the computation of $g(x)$. The <S-m-n theorem> gives a computable index map $e\mapsto p(e)$, and
$$
\varphi_{p(e)}=\begin{cases}g,&e\in K,\\\text{nowhere-defined function},&e\notin K.\end{cases}
$$
Consequently a decision procedure for membership in $C$ would decide the <halting set>. If the nowhere-defined <function> belongs to $C$, apply the same argument to its complement. \b[Every nontrivial extensional property of <partial computable functions> has an undecidable index <set>.] Syntactic properties of program descriptions are outside this assertion, and the theorem concerns unrestricted program indices, not merely an assumed list of terminating programs.
Here is an explicit <Jockusch triple coloring computing the halting set>. Choose computable increasing finite stages $K_s$ with <union> $K$. For $x<y<z$, put
$$
c(\{x,y,z\})=\begin{cases}0,&K_y\cap x=K_z\cap x,\\1,&K_y\cap x\ne K_z\cap x.\end{cases}
$$
This is a <computable colouring>. An infinite <monochromatic> <set> cannot have color $1$: fix its first element $x$ and choose two later elements beyond the stage at which $K_s\cap x$ stabilizes. Their triple has color $0$.
Suppose $H$ is infinite and homogeneous of color $0$. To decide whether $n\in K$ using $H$, find $x\in H$ with $x>n$, and then $y\in H$ with $y>x$. For every $z\in H$ above $y$, homogeneity gives $K_y\cap x=K_z\cap x$. Such $z$ are unbounded, so $K_y\cap x=K\cap x$. Testing $n\in K_y$ therefore decides $n\in K$. Hence every <homogeneous set> computes the <halting set>, and \b[there is no infinite recursive <monochromatic set>.] The <infinity> qualification is essential: finite <homogeneous sets> are recursive.
Back to article page
