Computable binary tree

A binary tree of finite strings is computable when membership of a finite binary string is decidable. An infinite computable tree need not have any computable infinite path. Removing all nodes without infinite extensions need not preserve decidability.

For an effective enumeration $({\phi }_e)$ of unary partial computable functions, admit a length-$n$ string $\sigma$ if it disagrees with every binary value of ${\phi }_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.

For a nonempty decidable binary tree of finite strings with no terminal nodes, begin at the empty string and repeatedly choose the first immediate successor that belongs to the tree. Each finite decision terminates and some successor always exists. This produces a total computable function giving an infinite path. In particular, a nonempty decidable tree in which every node has two incompatible extensions cannot have only noncomputable paths.