[FOM] Kleene tree variant

[Robert Lubarsky]

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.

 

Bob Lubarsky

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160119/b6ea2f3e/attachment-0001.html>