= Decidable tree for binary diagonal avoidance
For an effective enumeration $(\varphi_e)$ of unary <partial computable functions>, admit a length-$n$ string $\sigma$ if it disagrees with every binary value of $\varphi_e(e)$ observed within $n$ steps for $e<n$. The <bounded halting predicate> makes membership decidable, and the tests are prefix compatible. Its paths are exactly the <binary diagonally noncomputable functions>. The path space is nonempty and perfect because infinitely many indices of divergent programs leave arbitrarily late bits free; no path is computable. Dead ends in this decidable presentation are essential.
Back to article page
