# What is the extension of the truth-table degrees to Baire Space called?

Recall that for sets $A, B \in 2^\omega$ that we say $A \leq_{tt} B$ if there is a total Turing functional $F \colon 2^\omega \to 2^\omega$ such that $F(B)=A$. This is called truth-table reducibility. The equivalence classes are called the truth-table degrees. (The name "truth-table" has to do with another definition of this reducibility.)

It is easy to extend this definition to $\omega^\omega$. Namely $f \leq g$ if there is a total Turing functional $F \colon \omega^\omega \to \omega^\omega$ such that $F(g)=f$. It is fairly easy to see that (unlike Turing reducibility), this Baire space version gives a strictly larger set of degrees. (Just take a function $f \in \omega^\omega$ which grows faster than any computable function.)

Does the Baire space version of truth-table reducibility have a standard name? ("Truth-table" no longer seems appropriate here.)

Are there any standard references on it? (There are a number of papers and books exploring the truth-table degrees. I wonder if there are any looking into this version.)

Andrej Bauer asked for clarification on what I meant by total Turing functional. There are a large number of equivalent definitions of what it means for a function $F \colon 2^\omega \to 2^\omega$ or $F \colon \omega^\omega \to \omega^\omega$ to be computable. For example, $F$ is given by an oracle machine $M$ where $F(g)=f$ means that for all $n$, $M^g(n){\downarrow} = g(n)$. Here the machine $M$ can query the oracle $g$ for the value of $g(n)$. (One can also use monotone machines, type 2-machines, etc. One can also use computable analysis, but that is overkill since we are just working with the spaces $2^\omega$ and $\omega^\omega$ which can be found in any computability theory textbook.)

Total just means that $M^g(n)$ halts for all $g \in \omega^\omega$ and $n \in \omega$. (To be clear, I want $g \in dom(F)$ for all $g$, not just the computable ones---else the degree structure would be trivial.)

Total turing functional means a total computable function $F \colon \omega^\omega \to \omega^\omega$.

• What's a total Turing functional? Or to ask differently: how are input and output of $F : \omega^\omega \to \omega^\omega$ presented? By Turing codes or are we talking about Type II computability (aka function realizability)? May 21, 2016 at 19:16
• @AndrejBauer, I don't quite understand your question. I thought the relevant definitions were standard (or equivalent), but I added a section on what I mean. Let me know if you need further clarification. (I am not sure what you mean by "Turing codes", but to be clear, I need the functional to have a domain equal to all of $\omega^\omega$, not just the computable functions.) May 21, 2016 at 21:17
• Thanks for the clarification. I'd say that you're looking at oracle computations (rather than hereditarily effective operators, which would act only on computable inputs). May 22, 2016 at 16:51
• So, this looks a bit like a special case of Weihrauch reducibility. May 22, 2016 at 16:51
• @AndrejBauer, I believe you are mistaken. I don't believe these are a natural special case of the Weihrauch degrees. Instead the Turing degrees are a natural special case of the Weihrauch degrees corresponding to functions $F \colon \mathbb{N}^\mathbb{N} \to \mathbb{N}^\mathbb{N}$ which are constant and single-valued (i.e. $F$ ignores the input). Is that what you had in mind? May 23, 2016 at 13:26

The following is a generalization of Weihrauch reducibility to an arbitrary relative realizability model.

Let $A$ be a partial combinatory algebra and $A_{\#}$ a sub-PCA of~$A$. Write $\langle a, b\rangle$ for an encoding of an ordered pair in $A$ with components $a, b \in A$. Given $F \subseteq A \times A$, define the support $\|F\| = \{a \in A \mid \exists b \in A . (a,b) \in F\}$ and let $F[a] = \{b \in A \mid (a,b) \in F\}$.

Definition: Given $F \subseteq A \times A$ and $G \subseteq A \times A$, say that $F$ reduces to $G$, written $F \leq_W G$, when there exist $\kappa, \ell \in A_\#$ such that:

1. if $a \in \|F\|$ then $\kappa a$ is defined and $\kappa a \in \|G\|$,
2. if $a \in \|F\|$ and $b \in G[\kappa a]$ then $\ell \langle{a,b\rangle}$ is defined and $\ell \langle{a,b\rangle} \in F[a]$.

We obtain the usual Weihrauch degrees by instantiating $A$ and $A_\#$ with the second Kleene algebra and its recursive counterpart, respectively.

Given any $F \subseteq A \times A$, define $F^{*} \subseteq A \times A$ by $$F^{*} = \{ ([a_1, \ldots, a_n], [b_1, \ldots, b_n]) \subseteq A \times A \mid n \in \mathbb{N} \land \langle a_1, b_1\rangle, \ldots, \langle a_n, b_n\rangle \in F \}.$$ Here $[\ldots]$ is a suitable encoding of finite lists.

Now we instantiate the PCAs $A$ and $A_\#$ with Kleene's first algebra, i.e., $A = A_\# = \mathbb{N}$. We have: given $f, g \in 2^\omega$, viewed as functional relations, we have $f \leq_W g^{*}$ if and only if $f$ is truth-table reducible to $g$.

Let us work out what $f \leq_W g^{*}$ amounts to when $f, g \in \omega^\omega$, viewed as functional relations. By my calculation it is this: there exist partial computable functions $\kappa$ and $\ell$ such that, for all $a \in \mathbb{N}$:

1. $\kappa(a)$ is defined and is (the code of) a finite list of numbers $[a_1, \ldots, a_n]$ (where $n$ is computed from $a$, i.e., it is not fixed). Think of these as the questions which we're going to ask about $g$.
2. if $b$ is (the code of) a list $[b_1, \ldots, b_n]$ such that $g(a_i) = b_i$ for all $1 \leq i \leq n$ then $f(a) = \ell(\langle a, b\rangle)$. Think of the $[b_1, \ldots, b_n]$ as the oracle answers.

If I am not mistaken, this essentially amount to what you're asking for.

These results are joint work with Kazuto Yoshimura from JAIST. We're currently writing up a paper about a generalization of Weihrauch reducibilities (I gave a talk about it at the Logic Collouium 2014, but that is obsolete as we now have a much simpler definition of instance reducibility).

• For $2^\omega$ this is exactly truth-table reducibility. Indeed, $f \mapsto f^*$ is a very nice embedding of the truth-table degrees into the Weihrauch degrees since $f \leq_{tt} g$ iff $f^* \leq_W g^*$. HOWEVER, this does not work for my degree structure, since if $f < g$ in my degree structure there is no bound on how much of $g$ one needs to query to compute, say, $f(0)$. For example, consider $f(n) = g(g(n))$. May 23, 2016 at 19:18
• As I think about this more, your idea does not work even for truth-table reducibility---unless you make a significant change to (classical) Weihrauch reducibility. In classical Weihrauch reducibility, $\kappa$ and $\ell$ may be partial ($\kappa a$ need not be defined when $a \notin \|f\|$ and $\ell \langle a, b \rangle$ need not be defined when $b \notin G[\kappa a]$) which your generalization also allows. However, when you set $A=A_\# = \mathbb{N}$ you seem to switch to assuming $\kappa$ and $\ell$ represent total functions $\kappa, \ell \colon \mathbb{N} \to \mathbb{N}$. (continued...) May 23, 2016 at 21:22
• (...) Now, assuming you meant for $\kappa$ and $\ell$ to be partial: for $f, g \in 2^\omega$ then we have that $f \leq_W g^*$ iff $f \leq_{wtt} g$. (Here wtt means weak truth table reducibility and $f \leq_{wtt} g$ means that there is a function $\kappa \colon \mathbb{N} \to \mathbb{N}$ such that the computation of $M^g(n)$ only uses $g(0),\ldots,g(\kappa(n)-1)$ and $n$. This is close to, but a bit weaker than truth-table reducibility. (continued...) May 23, 2016 at 21:28
• (...) Assuming you meant for $\kappa$ and $\ell$ to be total: Then one can actually use my encoding from earlier. Namely, $f \leq g$ (in my reducibility) iff $f^{**} \leq_W g^{**}$ where $f^{**}, g^{**} \colon \omega^\omega \to \omega^\omega$ are the constant functions $f^{**}(-) = f$ and $g^{**}(-) = g$. (Also, if we can switch partial to total, we can say my reducibility is just a variation of Turing reducibility. :) ) May 23, 2016 at 21:35
• What you wrote is definitely weak truth table computability (for partial $\ell$). First, in computability terminology, $\kappa$ gives a bound on the use of the computation (that is, $\kappa(a)$ tells you the largest bit in $g$ one needs look at in order to compute $f(a)$---it can be different for each $a$). However, since $\ell$ is not total, we only need the support of $\ell$ to include the pairs $\langle a, g^* \kappa a \rangle$. That is, we only need $\ell$ to work for $g$, not all oracles. This is what distinguishes weak truth-table computability from truth table computability. May 24, 2016 at 4:09