= Solution
Take $\mathbb N=\{0,1,2,\ldots\}$ and fix a standard effective enumeration $(\varphi_e)$ of the unary <partial computable functions> by program texts. Write
$$
K=\{e:\varphi_e(e)\downarrow\},\qquad K_s=\{e<s:\varphi_e(e)\text{ halts within }s\text{ steps}\}.
$$
The <diagonal halting set> $K$ is not a <computable set>: a supposed decision procedure would give a program that halts on input $e$ exactly when $e\notin K$, contradicting its own index. Each $K_s$ is finite and uniformly decidable by <bounded simulation of a computation>, and $K_s\subseteq K_{s+1}$ with union $K$.
For $a<b<c$, define the <computable colouring>
$$
\boxed{\chi(\{a,b,c\})=\begin{cases}0&K_b\cap[0,a)=K_c\cap[0,a),\\1&K_b\cap[0,a)\ne K_c\cap[0,a).\end{cases}}
$$
This is a two-part decidable <set partition> on three-element subsets: sort the three inputs and perform the two finite simulations. Here $[0,a)=\{0,\ldots,a-1\}$. The <halting-stage colouring of triples> cannot have an infinite <homogeneous set for a colouring> of colour $1$. Indeed, fix its least element $a$. The finitely many bits of $K_s\cap[0,a)$ eventually stabilize. Choose two later elements $b<c$ of the putative <homogeneous set for a colouring> beyond that stabilization stage; the corresponding triple has colour $0$.
Now suppose $H$ is an infinite <homogeneous set for a colouring> of colour $0$. Its membership oracle computes $K$: to decide whether $n\in K$, search for $a,b\in H$ with $n<a<b$, and return whether $n\in K_b$. For every $c\in H$ above $b$, homogeneity gives $K_c\cap[0,a)=K_b\cap[0,a)$. Since $H$ is unbounded, taking such $c$ arbitrarily large proves that this common finite set is $K\cap[0,a)$. Thus
$$
K\leq_T H.
$$
If $H$ were a <computable set>, the displayed <Turing reduction> would decide $K$, a contradiction. \b[The displayed decidable two-colouring has no infinite decidable homogeneous set.]
For the second construction, let $2^{<\omega}$ be the finite <binary strings>, with coordinates starting at $0$, and define the <computable binary tree>
$$
\boxed{T=\{\sigma\in2^{<\omega}:\ \forall e<|\sigma|,\ \forall v\in\{0,1\},\ [\varphi_e(e)\text{ halts within }|\sigma|\text{ steps with output }v\ \Longrightarrow\ \sigma(e)=1-v]\}.}
$$
Membership is decided by finitely many tests using <bounded simulation of a computation>. It is a <binary tree of finite strings>: if a string satisfies the tests, each prefix satisfies its shorter and fewer tests. The <infinite paths through a binary tree> are exactly
$$
[T]=\{f\in2^\omega:\ \varphi_e(e)\downarrow\in\{0,1\}\Longrightarrow f(e)\ne\varphi_e(e)\text{ for every }e\}.
$$
This set is nonempty: at a coordinate whose diagonal computation halts with a binary value choose the other value, and choose either bit elsewhere. This is an existence argument, not a proposed computable decision procedure for convergence. No member is a <total computable function>. If $f=\varphi_d$ were a total binary-valued function, the condition at $d$ would say $f(d)\ne\varphi_d(d)=f(d)$. Thus each member is a <binary diagonally noncomputable function>.
Moreover, $[T]$ has no isolated point. There are arbitrarily large indices of programs that never halt: for example, distinct program texts with successively more unused instructions followed by an infinite loop provide infinitely many such indices in the usual syntactic program coding. At every one of these coordinates the bit is unrestricted. Given any $f\in[T]$ and any prefix length $n$, change its bit at one such index $e\geq n$ and leave all other bits unchanged. The resulting different path still belongs to $[T]$ and has the same length-$n$ prefix. Since a path space is closed in <Cantor space>, \b[$T$ is decidable, $[T]$ is nonempty and perfect, and no infinite path is computable.]
There is a definition issue with the adjective “perfect”. The preceding conclusion uses <perfect path space>, allowing finite dead ends in the decidable presentation. If “perfect tree” instead requires every node to have two incompatible extensions in the tree, the requested combination is impossible. Such a nonempty tree has no terminal nodes. Starting at the empty string, test the two immediate successors and choose the first that belongs to the tree; one always exists. This constructs a <total computable function> whose successive prefixes remain in the tree. Thus <computable pruned binary trees have computable paths>. Our $T$ necessarily has dead ends; its subtree consisting only of prefixes of infinite paths is perfect in the pruned sense but is not decidable. The construction therefore supplies the intended perfect closed path space and also resolves the stronger, inconsistent interpretation.
Back to article page
