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

Question

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

Answer 1

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