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

Turing degreesare 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? $\endgroup$ – Jason Rute May 23 '16 at 13:261more comments