5
$\begingroup$

The following definitions of a “transparent function” are essentially taken from references [1] (where it is called a “jump operator”), [2] and [3], except that the variation “primitively recursively transparent” and possibly another one is an addition of mine:

  • A partial function $U\colon \mathbb{N}\dashrightarrow\mathbb{N}$ is said to be transparent when for every partial computable $f\colon \mathbb{N}\dashrightarrow\mathbb{N}$ there exists $F\colon \mathbb{N}\dashrightarrow\mathbb{N}$ such that $U\circ F = f\circ U$. It is said to be computably transparent, resp. primitively recursively transparent when there is a computable (resp. a primitive recursive) $C$ which, when given a code for $f$, returns a code for $F$ as described. (Here, a “code” for a partial computable function is the number of a Turing machine which implements it.)

  • A partial function $U\colon \mathbb{N}^{\mathbb{N}} \dashrightarrow \mathbb{N}^{\mathbb{N}}$ is said to be transparent when for every partial continuous $f\colon \mathbb{N}^{\mathbb{N}}\dashrightarrow\mathbb{N}^{\mathbb{N}}$ there exists $F\colon \mathbb{N}^{\mathbb{N}}\dashrightarrow\mathbb{N}^{\mathbb{N}}$ such that $U\circ F = f\circ U$. It is said to be continuously transparent, resp. computably transparent when there is a continuous (resp. a computable) $C$ which, when given a code for $f$, returns a code for $F$ as described. (Here, a partial continuous function $\mathbb{N}^{\mathbb{N}}\dashrightarrow\mathbb{N}^{\mathbb{N}}$ means it is continuous and has a $G_\delta$ support¹; and a “code” in $\mathbb{N}^{\mathbb{N}}$ for such a function is as described in this question on the “second Kleene algebra”.)

I understand the text of these definitions in a formal sense, but I'm trying to get an intuitive grasp on what they really mean, what idea they're trying to capture and what motivates them (the references giving the definitions don't really explain much). I'm also very confused as to how the various versions above relate.

One essential idea, which I understand, is that if $U$ is a universal Turing machine with access to an oracle (or even a restricted oracle which the machine can call only once), then $U$ is computably transparent (indeed, p.r. transparent) because we can compute a code for $f\circ g$ from a code from $g$ (when $f$ is computable and $g$ is computable relative to the oracle in question). This is clear enough. But the identity function is also computably transparent (indeed, p.r. transparent) for trivial reasons, and it doesn't look at all like a universal Turing machine; more generally, any computable bijection is computably transparent (this one, on the other hand, can fail to be p.r. transparent): so I guess “some sort of universal Turing machine” is not the right intuition to have in mind for transparency.

(Also, just like I can find an example of a computably transparent function $\mathbb{N}\to\mathbb{N}$ that is not p.r. transparent by considering a computable but not p.r. bijection, I can find an example of a continuously transparent function $\mathbb{N}^{\mathbb{N}}\to\mathbb{N}^{\mathbb{N}}$ that is not continuously transparent by considering a continuous bijection that is not computable, but it still doesn't enlighten me much as to how different these notions are.)

Questions (which can probably be answered together):

  • What idea are these definitions really trying to capture?

  • What are some interesting (and if possible, illuminating) examples of the various kinds of transparent functions beyond the ones already mentioned above?

  • Specifically, what is an example of a transparent $U\colon \mathbb{N}\dashrightarrow\mathbb{N}$ that is not computably transparent, if such exists?

  • Similarly, what are examples showing that that for $U\colon \mathbb{N}^{\mathbb{N}} \dashrightarrow \mathbb{N}^{\mathbb{N}}$, the conditions “transparent” and “continuously transparent” differ (if indeed they do)?

Footnote:

  1. To be honest, I'm also not sure about this “$G_\delta$ support” bit. The references below don't really make it clear that “partial continuous” is to be interpreted that way, and it's not clear to me whether this matters or it's just a red herring. But the code in $\mathbb{N}^{\mathbb{N}}$ encodes partial continuous functions with $G_\delta$ support, so I guess it should be there. Anyway this is probably not too important for my question.

References:

  1. Matthew de Brecht, “Levels of discontinuity, limit-computability, and jump operators” in: Vasco Brattka, Hannes Diener & Dieter Spreen (eds.), Logic, Computation, Hierarchies (2014); arXiv link

  2. Vasco Brattka, Guido Gherardi & Alberto Marcone, “The Bolzano-Weierstrass Theorem is the Jump of Weak Kőnig's Lemma”, Ann. Pure Appl. Logic 163 (2012), 623–655; arXiv link

  3. Takayuki Kihara, “Rethinking the notion of oracle”; arXiv link

$\endgroup$

1 Answer 1

4
$\begingroup$

The intuition for transparency functions is the following (then all the other notions are slight variations): if you are trying to apply some $f$ after $U$, this is indeed the same as applying some other $F$ before $U$. This may be useful in the context e.g. of Weihrauch reducibility: indeed, a Weihrauch reduction to $U$ involves a preprocessing and a post-processing phase. If you are computably transparent then essentially you do not need the post-processing phase, as you can embed that in the preprocessing one.

Computably/continuously transparent simply means that you can go from $f$ to $F$ in a computable/continuous way. Here is where the $G_\delta$ domain comes into play: when $f$ is computable you can think of the index of $f$ to be just a natural number. When $f$ is continuous, you should fix an enumeration $(\Phi_p)_{p\in\mathbb{N}^\mathbb{N}}$ of a large enough class of continuous functions. It suffices to consider functions with $G_\delta$ domain as every continuous function can be extended to one with $G_\delta$ domain.

In [1], the authors claim that $\lim$ is transparent. This is actually fairly easy to see (as the functions involved are continuous), but I feel it helps having an intuition. Another example is the problem: given an ill-founded tree in the Baire space with a unique path, produce it.

I don't really have an answer for the last two points from the top of my head, but maybe it's not that hard to explicitly find some (artificial) one.

[1]: Brattka, Vasco; Gherardi, Guido; Marcone, Alberto, The Bolzano-Weierstrass theorem is the jump of weak Kőnig’s lemma, Ann. Pure Appl. Logic 163, No. 6, 623-655 (2012); addendum ibid. 168, No. 8, 1605-1608 (2017). ZBL1245.03097.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .