Domain of a Type-2 Computable Function

Question

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.

Answer 1

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.

Answer 2

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.