In Classical Recursion Theory Vol.I by P.Odifreddi, section V.5 on the Tree Method, the proof for the existence of hyperimmune-frees involves the construction of a series of trees. Some definitions first:

  • Tree: a function from initial segments to initial segments (binary) s.t. (1) $T(\sigma)\downarrow \wedge \tau \subseteq\sigma \rightarrow T(\tau)\downarrow \wedge T(\tau) \subseteq T(\sigma)$; (2) if one of $T(\sigma * 0), T(\sigma * 1)$ is defined, both are defined and incompatible.
  • A is a branch of tree T if $T(\sigma) \subseteq A$ for infinitely many $\sigma$'s;
  • Q is a subtree of T ($Q \subseteq T$) if for every $\sigma \in ran(Q), \sigma \in ran(T)$

My question is concerning the following technical lemma:

$Lemma (Totality)$: Given $e$ and a recursive tree $T$, there is a recursive tree $Q \subseteq T$ s.t. one of the following holds:

  • for every branch $A$ on $Q$, {$e$}$^A$ is not total;
  • for every branch $A$ on $Q$, {$e$}$^A$ is total and $(\forall n)(\forall \sigma)(|\sigma|=n \rightarrow ${$e$}$^{Q(\sigma)}(n)\downarrow)$

Ideas in the proof: First step is to see whether the following condition is fulfilled, $(\exists \sigma \in T)(\exists x)(\forall \gamma \supseteq \sigma)(\gamma \in T \rightarrow ${$e$}$^{\gamma}(x)\uparrow)$. If it exists, the first condition the fulfilled since we can take the full subtree above $\gamma$ on $T$. If not, $Q(\emptyset)= least$ $\gamma\in T$ s.t. {$e$}$^\gamma \downarrow$, inductively, for $Q(\sigma)$ there is an extension of it $T(\gamma)$ on $T$ s.t. {$e$}$^{T(\gamma)}(|\sigma|)\downarrow$, let $Q(\sigma *i) = T(\gamma * i)$, for $i=0,1$.

But is the following assertion true? {$e$}$^A (n) \leq max_{|\sigma|=n}$ {$e$}$^{Q(\sigma)}(n)$, for any branch A on Q s.t. {$e$}$^A$ is total. The claim in the book is it is true since {$e$}$^A(n)$ is already defined on the $n^{th}$ level of the tree $Q$. However, is it reasonable to consider the possible e-splitting as well, namely, $\tau_1, \tau_2$ are two different strings s.t. {$e$}$^{\tau_1}\downarrow,$ {$e$}$^{\tau_2}\downarrow$ but they are not equal? The above construction only makes sure the existence of the value on the n$^{th}$ level, but will the value change later on?

  • 2
    $\begingroup$ I think this is just a matter of convention - the only reason why $\phi^\tau_e(n)$ would change later on would be if the algorithm read beyond $\tau$ and made a decision contingent on the absence of a value there. Since this is somewhat silly, it is safe to assume that the algorithm diverges as soon as it attempts to read beyond $\tau$. This way, the output of the algorithm will agree on any longer oracle. $\endgroup$ Commented Jun 28, 2012 at 19:33
  • $\begingroup$ Thank you @Francois. What you suggested totally makes sense. I think I just got confused at when to think of splitting. I referred to the previous discussion in the book, the situation is only considered when the function under current string(oracle) is undefined. Thank you for enlightening me! $\endgroup$
    – Jing Zhang
    Commented Jun 29, 2012 at 7:44

1 Answer 1


You have to be careful here and realize that $Q(\sigma)$ is a function from $2^{<\omega}$ to $2^{<\omega}$ and thus $Q(\sigma)$ can be arbitrarily long even if $|\sigma|=n$.

When the construction makes use of the second case $Q(\emptyset)$ is defined so that ${e}^{Q(\emptyset)}(0)\downarrow$. Now, as you observed, if $Q$ is defined for all $\sigma$ of length $n-1$ we can define it for all $\tau=\sigma*i$ of length $n$ by setting $Q(\sigma*i)$ to be $T(\gamma*i)$ where $\gamma$ is the string with the least code satisfying $T(\gamma) \supseteq Q(\sigma)$ and ${e}^{T(\gamma)}(n)\downarrow_{|T(\gamma)|}$. Such a $\gamma$ must exist since otherwise $Q(\sigma)$ would lack any extension on $T$ causing the $e$-th functional to converge on $n$.

I've spelled out the definition of $Q$ a little more pedantically to illustrate why the claim holds. Given $Q$ built in this fashion if $A$ lies on $Q$ then $A$ (viewed as a string) equals $\cup_{k \in \omega} Q(f\restriction_k)$ for some $f \in 2^\omega$. Thus, given $n$, $A$ extends $Q(\tau)$ where $\tau=f\restriction_{n+1}$ and by construction ${e}^{Q(\tau)}(n)\downarrow_{|Q(\tau)|}$ (as $Q(\tau)=Q(\sigma*i)=T(\gamma*i) \supseteq T(\gamma)$). Hence, if $A$ on $Q$ then

$$(\exists \tau)(|\tau|=n \land {e}^{A}(n)\downarrow={e}^{Q(\tau)}(n)\downarrow_{|Q(\tau)|})$$.


$${e}^{A}(n)\downarrow \leq \max_{|\tau|=n} {e}^{Q(\tau)}(n)\downarrow_{|Q(\tau)|})$$ where the right hand side is well-defined since by construction if $|\tau|=n$ then ${e}^{Q(\tau)}(n)\downarrow_{|Q(\tau)|})$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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