The (a?) Kleene tree is a computable (a.k.a. decidable) sub-tree of the full binary tree with no computable path. It is well-known.


I need a variant. (For those in the know, I need a c-bar which is not a D-bar.) What I need is also based on a computable labeling of the binary tree. With the Kleene tree, once a binary sequence gets kicked off the tree, all of its descendants are kicked off too, else it wouldn’t be a tree. So you can think of a Kleene tree as a computable labeling of binary sequences by “in” and “out”, where once a sequence is “out” so are all of its descendants. In the tree I need, if a sequence is labeled “out,” a descendant is allowed to be labeled “in”. A sequence is really off the tree when it AND all of its descendants are labeled “out”. This is a $\Pi^0\_1$ condition, hence not computable (at least, not obviously computable). A sequence is in the tree when some descendant is labeled “in”. 


What I need is a tree like that, with no computable paths, not equal to any Kleene tree. Anyone know one? Or how to do it? Presumably some priority argument would suffice.



a variant of the Kleene tree
Let $K\_s$ be a computable monotone sequence of finite sets whose union is $K$, the halting set. Let $T$ be the tree of all $\{0,1\}$-sequences $\tau$ such that for some $s \geq |\tau|$, $\tau$ is the characteristic function of $K\_s \cap \{0,\ldots,|\tau|-1\}$. The tree $T$ is of the type you want and its only infinite path is the characteristic function of $K$. $T$ cannot be a Kleene-type tree because of the Low Basis Theorem.


