2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – Andrej Bauer May 21 '16 at 19:16
  • 1
    $\begingroup$ @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.) $\endgroup$ – Jason Rute May 21 '16 at 21:17
  • $\begingroup$ 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). $\endgroup$ – Andrej Bauer May 22 '16 at 16:51
  • $\begingroup$ So, this looks a bit like a special case of Weihrauch reducibility. $\endgroup$ – Andrej Bauer May 22 '16 at 16:51
  • $\begingroup$ @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? $\endgroup$ – Jason Rute May 23 '16 at 13:26
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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))$. $\endgroup$ – Jason Rute May 23 '16 at 19:18
  • $\begingroup$ 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...) $\endgroup$ – Jason Rute May 23 '16 at 21:22
  • $\begingroup$ (...) 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...) $\endgroup$ – Jason Rute May 23 '16 at 21:28
  • $\begingroup$ (...) 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. :) ) $\endgroup$ – Jason Rute May 23 '16 at 21:35
  • $\begingroup$ The functions $\kappa$ and $\ell$ are partial. It turns out that in the case $F \subseteq \mathbb{N} \times \mathbb{N}$ is the graph of a function $f \in \omega^\omega$ then $\kappa$ is total (because $\|f\| = \mathbb{N}$), but $\ell$ is still partial. Thanks for catching this, and also for pointing out this is weak truth table reducibility. I am going t ofix the answer. So we need something else for truth table reductions. $\endgroup$ – Andrej Bauer May 23 '16 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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