 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 $({\phi }_e{)}_{e\in \omega }$ of the partial computable functions, with a universal partial computable function $U(e,x)={\phi }_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:{\phi }_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 ${\phi }_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)$, andConsequently 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. 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$, putThis 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 there is no infinite recursive monochromatic set. The infinity qualification is essential: finite homogeneous sets are recursive.