patternMinor
Domain of a Type-2 Computable Function
Viewed 0 times
typefunctiondomaincomputable
Problem
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.
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.
Solution
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:
-
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.
-
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.
-
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.
-
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.
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:
-
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.
-
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.
-
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.
-
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.
Context
StackExchange Computer Science Q#125869, answer score: 4
Revisions (0)
No revisions yet.