5
$\begingroup$

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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks Francois. This probably suffices for my ultimate use. I still find it odd that there's this example with just one path. The regular Kleene tree has lots of paths. I wonder whether there's an example (of the type I asked for) that looks more like the Kleene tree, bushier, with continuum many paths. $\endgroup$
    – Robert Lubarsky
    Commented Jan 25, 2016 at 3:28
  • $\begingroup$ @RobertLubarsky Easily arranged! Given a tree $T$, let $\hat{T}=\{\sigma: (\sigma(0), \sigma(2), \sigma(4), . . . , \sigma(2k), . . )\in T\}$; then every path through $\hat{T}$ computes a path through $T$, and $\hat{T}$ is of the same complexity as $T$, but $\hat{T}$ has continuum-many paths. $\endgroup$
    – Noah Schweber
    Commented Jan 25, 2016 at 3:57
1
$\begingroup$

Let $\sigma_i=0...01$ ($i$ many $0$s). We can build a $\Pi^0_1$ tree $T$ such that $\sigma_i\in T$ iff the $i$th c.e. tree either does not contain $\sigma_i$, or eventually kills all extensions of $\sigma_i$; this involves killing $\sigma_i$ at first if $\sigma_i$ appears on the $i$th computable tree, then perhaps bringing back $\sigma_i$ at a later date. Meanwhile, above each $\sigma_i$ we don't kill (or do bring back), we repeat the usual construction of an infinite computable tree with no computable paths.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I can't get off the ground with this answer. The problem I have with it is right up front: what is the $i$th computable tree? I know what the $i$ computable function is, and the $i$ c.e. set. But given a program, I can't tell whether it determines a computable set or not. $\endgroup$
    – Robert Lubarsky
    Commented Jan 25, 2016 at 3:26
  • $\begingroup$ @RobertLubarsky Sorry, I should have said "$i$th c.e. tree." The point is, for a fixed Turing machine $\Phi_i$, I keep $\sigma_i$ on the tree I'm building - until $\Phi_i(\sigma_i)\downarrow=1$ (as well as for every predecessor of $\sigma_i$). then I kill $\sigma_i$, and only bring it back if for some $n$, I see $\Phi_i(\tau)\downarrow=0$ for every extension $\tau$ of $\sigma_i$ of length $n$. $\endgroup$
    – Noah Schweber
    Commented Jan 25, 2016 at 3:44
  • $\begingroup$ I finally understand your construction. It seems to work. Thanks. Also for your comment on my comment on Francois's answer. Honestly, wasn't that hard. I feel dumb. $\endgroup$
    – Robert Lubarsky
    Commented Jan 26, 2016 at 13:09
  • $\begingroup$ Wait a minute. The 0 sequence is a computable path through your tree. $\endgroup$
    – Robert Lubarsky
    Commented Jan 26, 2016 at 14:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .