Computable colouring ($\chi :[\mathbb{N}{]}^r\to k$)

A colouring is computable when an algorithm sorts the finite input subset, computes its colour and terminates. Its colour classes are uniformly computable sets. The distinction between existence of an infinite homogeneous set for a colouring and effective construction of one is a basic phenomenon in computability theory.

There is a two-colour computable colouring of pairs with no infinite computably enumerable set homogeneous for it. Enumerate these sets as $W_e$. In stages, give each eligible requirement two markers from its enumerated set, avoiding markers of higher priority, and cancel all lower-priority markers whenever a new assignment is made. Colour $(x,y)$ by the marker status of $x$ at stage $y$: first markers have colour zero, second markers colour one, and unmarked points colour zero. Each requirement is injured only finitely often by induction on its index. If $W_e$ is infinite it eventually has permanent distinct markers $a_e,b_e$; for every sufficiently large $y\in W_e$, the pairs $(a_e,y)$ and $(b_e,y)$ have different colours. Simulating finitely many stages computes each pair's colour, proving both effectiveness and the obstruction.

Let $K_s$ be an increasing uniformly computable finite approximation to the diagonal halting set. For $a<b<c$, colour the triple $0$ if $K_b\upharpoonright a=K_c\upharpoonright a$, and $1$ otherwise. No infinite homogeneous set for a colouring can have colour $1$, since the finitely many bits below its first element eventually stabilize. Every infinite homogeneous set $H$ of colour $0$ computes the diagonal halting set: choose $n<a<b$ in $H$ and read membership of $n$ in $K_b$. Homogeneity and unboundedness make this answer final. Thus the colouring has no infinite computable homogeneous set.