= Computable pruned binary trees have computable paths
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.
Back to article page
