2
$\begingroup$

In Weihrauch's Type-2 computability theory, a string function $f\colon\subseteq \Sigma^{\omega}\rightarrow \Sigma^{\omega}$ (the $\colon\subseteq$ indicates that $f$ may be a partial function) is computable iff there exists a Type-2 Turing machine that exactly realizes $f$, which implies that the Turing machine must fail to produce an output on inputs that are not in the domain of $f$.

To extend this to functions between arbitrary domains $D_1$ and $D_2$, one specifies representations $\gamma_i\colon\subseteq\Sigma^{\omega}\rightarrow D_i$, and Weihrauch defines $f\colon\subseteq D_1\rightarrow D_2$ to be $(\gamma_1,\gamma_2)$-computable iff there exists a Type-2 computable string function $g$ such that $f(\gamma_1(y)) = \gamma_2(g(y))$ whenever $f(\gamma_1(y))$ is defined.

But $\gamma_2(g(y))$ is allowed to be defined even when $f(\gamma_1(y))$ is not.

Why is it defined this way? It seems to me more natural to require $f\circ\gamma_1 = \gamma_2\circ g$, i.e. the domain of the realization $g$ must match the domain of $f$. With Weihrauch's definition we have the odd condition that, for a string function $f$, the statements "$f$ is Type-2 computable" and "$f$ is $(\mathrm{id},\mathrm{id})$-computable" (where $\mathrm{id}$ is the identity function) are not equivalent.

Reference: Weihrauch, K. (2000), Computable Analysis: An Introduction, Springer.

$\endgroup$
2
  • $\begingroup$ Are you looking for an explanation in terms of category theory or at an intuitive level? $\endgroup$ – Andrej Bauer May 18 '20 at 7:27
  • $\begingroup$ Intuitive level. In particular, why does it make sense to define things in such a way that an uncomputable string function $f$ may nonetheless be considered computable if we regard $\Sigma^{\omega}$ as just another arbitrary domain and use the definition of computability for arbitrary domains? $\endgroup$ – Kevin S. Van Horn May 18 '20 at 23:54
3
$\begingroup$

Philosophical answer

The general philosophy in realizability theory (TTE is a special case of it) is that for a program $p$ realizes a map $f : A \to B$ then $p$, it should work correctly on realizers of arguments, i.e., if $r$ realizes $x \in A$ then $p\,r$ realizes $f(x) \in B$. It is quite unnatural to say anything about "non-realizers", for at least two reasons. First, it would break the categorical structure of the category of representations (exponentials break). Second, from the programming point of view you are asking that a program always produce garbage output when given garbage input. This is an unreasonable request: the behavior should be unspecified for garbage input, as a program may in fact be unable to tell that it was given garbage input.

Technical answer

We are in the realm of realizability theory, of which TTE is a special case. It is important to understand that, when working with representations, there are two notions of function:

  1. The maps which take realizers to realizers, in the case of TTE these are the maps $\Sigma^\omega \to \Sigma^\omega$. Let us call these realizers.

  2. The morphisms in the category of represented sets, which are maps between sets that are tracked by a realizers. In TTE these are also called $(\gamma_1, \gamma_2)$-computable maps, but we shall just call them morphisms.

Standard textbooks on computability theory almost alawys talk about the first notion. The question is asking about the relationship between the first and the second notion.

Typically realizers are not actually functions, but are elements of some model of computation, such as Turing machines (either type I or type II) or the closed terms of $\lambda$-calculus. In the case of Type Two Effectivity this becomes apparent once we try to compute the standard representation for the set of realized maps, because that is when we define what it means for an element of $\Sigma^\omega$ to implement a realizers $\Sigma^\omega \to \Sigma^\omega$.

Morphisms between represented sets are functions (which happen to be tracked by a realizer).

Let us consider the question "Is the restriction of a computable map also computable?" in both senses.

  1. Is the restriction of a realizers (as a map) again a realizer? The answer is negative, for if $f {:}{\subseteq} \Sigma^\omega \to \Sigma^\omega$ is computed by a Turing machine, one can show that the domain of $f$ is a $G_\delta$-set. Therefore, if we restrict $f$ to a domain which is not a $G_\delta$-set there will be no Turing machine that computes the restriction.

  2. Is the restriction of a morphism $f : D_1 \to D_2$ again a morpshism? Here we have to understand "restriction" in the sense of category theory, i.e., a precomposition with a (regular) mono. This amounts to restricting the representation $\gamma_1 : \Sigma^\omega \to D_1$ to a subset $D \subseteq D_1$. We could define the realizability model so that restrictions need not be realized, but that would be silly and useless. It is much better to make sure that the resulting category has good properties, because then we can actually do something with it. And so we define the notion of "tracked by a computable map" in the way we do and enjoy the resulting ambient.

$\endgroup$
3
  • $\begingroup$ Minor comment: the second part of the answer is more interesting. The first part is rather counter-intuitive, since if an arbitrary restriction of a computable partial function does not have to be computable, in general. E.g. a set is RE iff its semi-characteristic function is partial computable. Any semi-char. is a restriction of the constant one function, but that doesn't make it computable (or every set would be RE). Hence, this computability notion ("we only care about realizers") seems to follow a slightly different intuition compared with the "basic" computability notion. $\endgroup$ – chi May 18 '20 at 22:52
  • 1
    $\begingroup$ @Andrej, you say it's reasonable to expect the restriction of a computable map to be computable, but my textbook definition of (standard, Type-I) computability does not have this property for either string functions nor arbitrary domains, nor does Weihrauch's definition of Type-II computability for string functions. Why does your argument not apply in these cases? $\endgroup$ – Kevin S. Van Horn May 19 '20 at 0:04
  • $\begingroup$ As @chi points out, there are two different things: computable functions as programs or realizers (which is what your textbook is talking about) and computable morphisms in a realizability model (which is what you are asking about). I'll amend my answer as this is not clearly pointed out. $\endgroup$ – Andrej Bauer May 19 '20 at 8:33
1
$\begingroup$

Andrej's answer raises some excellent points. I think we can gain some additional insight by looking at why we demand the computable partial functions come with their natural domain in classical computability theory.

One benefit we get from this is that in Type-1 computability a string function computation can only provide garbage in a very limited way: It either halts and provides an output, or it does not halt. Requiring that halting always indicates a valid input and subsequent valid computation means that we can trust any output we see. Already for a Type-2 computation on infinite sequences, invalid output can be more complicated, as we can see some finite prefix of an input before the computation stalls (the natural domain of a Type-1 computation is $\Sigma^0_1$, that of a Type-2 computation is $\Pi^0_2$). As soon as we move to more complicated represented spaces, garbage outputs can be arbitrarily hard to detect - so there is no gain in information coming from a requirement that garbage input must yield garbage output.

A second reason that we do want the set of computable partial functions to be countable, and in fact, want to have a standard enumeration of it. This motivation carries over to Type-2 computable partial functions of type $\Sigma^\omega \to \Sigma^\omega$, which we use as realizers. However, we (almost) never care about the set of partial computable functions from one represented space to another. We either speak about the set/space of computable total functions (which is countable without any garbage-in/garbage-out requirements, and in fact better behaved without); or we say that an individual partial function is computable. So this reason does not apply here, either.

$\endgroup$
2
  • $\begingroup$ Thanks, this was quite useful. BTW, I'm currently looking at a case where we do care about partial computable functions $f\colon\subseteq\Sigma^{\omega}\rightarrow D$: random variate generators that map a random string of bits into a draw from some distribution on $D$. These functions can be partial, as long as the domain has measure 1. $\endgroup$ – Kevin S. Van Horn May 19 '20 at 13:58
  • $\begingroup$ @KevinS.VanHorn I would tend to assume that you wouldnt actually work with the space of partial computable functions with full measure domain here, but rather with some quotient of it. But these are the kind of things that caused me to put the "almost" in there. $\endgroup$ – Arno May 19 '20 at 14:32

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.