Showing that if $f$ is the only limit point in a computable tree $T$ then $f\leq_T\emptyset''$.

Question

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!

Answer 1

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.

Answer 2

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$.