1
$\begingroup$

I am currently working through Soare's Computability text and am going over the section on binary trees (Chapter 8). I got to the following question: Let $T$ be a computable tree (in $2^\omega$) and assume $[T]$ has only one limit point, $f$. Show that $f\leq_T\emptyset''$.

Here we have that a computable tree $T$ is a computable set closed under initial segments, i.e. $\sigma\in T$ and $\tau\prec\sigma$ implies $\tau\in T$ and $[T]$ denotes the set of infinite paths in our tree $T$, i.e. $\{f\colon (\forall n)[f\!\upharpoonright\! n\in T]\}$ while $\emptyset''$ denotes the Turing Jump of the Halting Problem.

In order for $f$ to be a limit point of $[T]$ we must have that, $\forall\sigma\in F$, there exists $\tau\in T$ such that $\sigma\preceq\tau$ or $\tau\prec\sigma$ and $\tau\not\in f$ (i.e. $f$ is not an isolated path and thus contains no atom). After this observation, however, I was at a loss on where to go from here in order to prove that $f$ is $\emptyset''$-computable since I cannot seem to come up with an algorithm that avoids isolated paths in $[T]$. Any help would be greatly appreciated!

$\endgroup$
1
$\begingroup$

You can compute $f$ from $0''$ as follows.

First, notice that even $0'$ knows whether a given node $\sigma$ in the tree lies on a branch, since you just have to ask whether $\sigma$ has infinitely many extensions in the tree, and this is a $\Pi^0_1$ question that $0'$ can therefore answer.

Next, among the nodes $\sigma$ that do lie on a branch, using $0''$ we can recognize whether $\sigma$ lies on two or more different branches, since this is equivalent to asking whether there are two incomparable extensions of $\sigma$, each of which lie on a branch. This is a $\Sigma^0_2$ question about $\sigma$ that $0''$ can answer.

Now, the key observation is that if $\sigma$ lies only on isolated branches, then since Cantor space is compact, it follows that $\sigma$ lies on only finitely many isolated branches (since any infinite set would have a limit point). So therefore, there will be a level in the tree by which time all those finitely many branches have separated from one another. So with a $0''$ oracle, we can search for a level in the tree such that all extensions of $\sigma$ on that level lie on at most one path. In this way, we recognize that $\sigma$ lies on only isolated branches.

In this way, we can systematically enumerate, with a $0''$ oracle, all the nodes that do not lie on the unique limit-point branch. When all nodes on a given level have been excluded in this way except one, then we know that that node is the node that lies on the limit-point branch.

$\endgroup$
3
  • $\begingroup$ +1, and note for the OP that this scales upwards: e.g. if $T$ has exactly one limit-of-limit paths, that path is computable from $0'''$, and so forth. Indeed there's a tight connection between the hyperarithmetic hierarchy and the Cantor-Bendixson rank here, with things getting more complicated as we move from trees with unique paths of high rank to analyzing the complexity of high-rank paths through trees with many of them (e.g. projecteuclid.org/euclid.jsl/1183743032). $\endgroup$ – Noah Schweber May 10 '17 at 17:23
  • $\begingroup$ Thanks! This is an interesting approach and quite different from what I was thinking. I was wondering if you could also provide a hint on as to what the necessary requirements would be such that this path $f$ would also have that $0''\leq_T f$? I'm having a bit of trouble seeing how one could construct a computable tree s.t. this limit point path could compute $0''$. $\endgroup$ – K. Dar May 11 '17 at 12:59
  • $\begingroup$ To get $0''\leq_T f$, I would try to build a tree $T$ so that the limit branch witnesses a complete $\Pi^0_2$-set. Those sets have the form $\forall n\exists k\ \varphi(n,k,x)$, where $\varphi$ is decidable. So somehow the branch should enable you to know of a given $x$ whether every $n$ has it's $k$. To get just one limit branch, I'd say that the other branches are giving the information about the first finitely many such $x$'s, but more and more in a way that converges, and so the limit branch gives all the information. $\endgroup$ – JDH May 11 '17 at 13:12
1
$\begingroup$

Joel's answer is absolutely correct; let me give another take on really the same idea, phrased differently (in terms of limit computation), which (relativized appropriately) says that a set is computable in $A'$ iff it is limit computable in $A$. Here $A=0'$; we want to limit-compute $f$ using $0'$.

So how do we do this? Well, our one actual use of $0'$ is to "prune the tree" - replace $T$ with the subtree $T^*=\{\sigma\in T: \exists g\in [T], \sigma\prec g\}$ of extendible nodes. We then limit-compute via $T^*$, by "guessing" whether a node lies on the nonisolated path $f$ or not.

Intuitively, when we see a branching occur above a node $\sigma\in T^*$, we see another path going through $\sigma$ (since each node is extendible), so it seems more likely that $f$ goes through $\sigma$ ($f$ is nonisolated, so it's "surrounded" by lots of paths; if $\sigma\prec f$ we will see lots of splitting above $\sigma$!). In fact, the following is true, and a good exercise (it's essentially a higher version of Konig's lemma):

$\sigma\prec f$ iff $T^*$ has infinitely many splitting nodes above $\sigma$.

One direction is trivial; for the other, the key is to observe via Konig's lemma that any binary tree with infinitely many paths has a limit path.

So how do we figure out what $f$ is "in the limit"? Well, let's think about figuring out the first bit of $f$ - does $f$ start with a $0$ or a $1$? Well, we search down the tree node by node, and at any given moment our "current guess" about $f(0)$ is $0$ if we most recently saw a splitting above $\langle 0\rangle$, and $1$ if we most recently saw a splitting above $\langle 1\rangle$ (and to get things started, let's say $f(0)=0$ at the start, but this is arbitrary). By the previous paragraph, eventually we "run out" of splitting nodes above one node but not above the other, so our guess settles down to the right value. Similarly, but a bit messier to write down, we can limit compute $f(n)$ for each $n$.

$\endgroup$
1
  • $\begingroup$ Thanks! This is the approach I was thinking of but had failed to come up with some of the details to. I was wondering if you could also provide a hint on as to what the necessary requirements would be such that this path $f$ would also have that $0''\leq_T f$? I'm having a bit of trouble seeing how one could construct a computable tree s.t. this limit point path could compute $0''$. $\endgroup$ – K. Dar May 11 '17 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.