The classical computability theory taking place in $\mathbb{N}$, can be extended to more general spaces, like $T_0$ second countable topological spaces $(X, \mathcal{O}, v)$ where $\mathcal{O}$ is a countable basis of $X$ and $v:\mathbb{N} \rightarrow \mathcal{O}$ a total surjection. Then we say that $f:X \rightarrow Y$ is computable if given any enumeration of all basic open sets containing $x$, one can compute (in the sense of Turing) an enumeration of all basic open sets contaning $f(x)$. Equivalently we can state that for any basic open set $O$ of $Y$, we have that $f^{-1}(O)$ is a recursively enumerable open in the sence that $f^{-1}(O)=\cup_n O_n$ where $O_n$ is a recursively enumerable sequence of basic open sets of $X$

This brings some sort of a generalization of Turing reduction, when $X$ and $Y$ are both the Cantor space.

Now, I am wondering if it is possible to have a categorical point of view on all this. My research brought me to Topoi, the effective topos and the recursive topos. I have some difficulties to understand what is the effective topos (as I have to understand what is the recursive topos).

Before I spend a lot of time to study them, I would like to know if there are somehow related to what I've stated above (i.e., does one of them contains in some way the computable functions between topological spaces ? is there only continuous functions between topological spaces in these Topos ? can we even talk about topological spaces in these topos ?) or are hey something completely different ?

I apologize if my question seems too general. Any answer will be appreciated :)

  • 1
    $\begingroup$ A typo in the first paragraph: you seem to want $f^{-1}(O)$ to be that union, rather than $O$. But also, could you say a little more about why those two characterizations are equivalent? And you really don't want to insist on any uniformity in those computability requirements? $\endgroup$ – Joel David Hamkins Dec 2 '11 at 18:00
  • 2
    $\begingroup$ One must insist on some degree of uniformity in the algorithm to get equivalence: otherwise, in the discrete space of $\mathbb{N}$, every function $f:\mathbb{N}\to\mathbb{N}$ is computable in the first sense, since for any $x$ the only basic open set containing $f(x)$ is {f(x)}, which can be enumerated. But the characteristic function of a c.e. noncomputable set will not be computable in the second sense. $\endgroup$ – Joel David Hamkins Dec 2 '11 at 19:04
  • $\begingroup$ I can help with your question if you tell me a little more about what it is you are doing. Are you studying computable topology and would like references? How did your research "bring you to toposes, the effective topos and the recursive topos"? As Joel noticed already, your definition of computable maps lacks uniformity. $\endgroup$ – Andrej Bauer Dec 3 '11 at 0:35
  • $\begingroup$ Yes yes, I am very sorry about that, of course uniformity is required, otherwise it does not make much sence ! My 'research' brought me to toposes while I was trying to get a space of functions between two computable topological spaces, where computable functions would be computable points of this space. But then I thouht that I can maybe get more than just exponentiation... $\endgroup$ – Archimondain Dec 3 '11 at 1:48

There are many realizability toposes, of which the effective topos is just one. Each realizability topos has its own internal language in which topology and analysis can be developed to a considerable degree. Thus we get many notions of computable topology, not just one.

If you are interested in computable topology in the effective topos specifically, but would like to study the topic without first learning the machinery, you should look at Dieter Spreen's paper On Effective Topological Spaces.

If you are just getting into the topic of computable analysis, you should look at Klaus Weihrauch's Computable Analysis: an introduction.

If you would like to understand more generally why there are many kinds of computable topology, not just one, you can read my Ph.D. thesis. This may also serve as a general introduction to computable analysis and topology.

| cite | improve this answer | |
  • $\begingroup$ Thank you for your answers. I will look attentively to your phd thesis, which seems very interesting. In fact I'am just starting a phd myself (on the more or less unrelated subject of computable randomness but I am interested in everything about computability). I do not know a lot of things yet, especially in Category theory. But I guess some work would worth it, seens it seems that the topological spaces I currently use to work with can be 'a part' of a realizability toposes. $\endgroup$ – Archimondain Dec 3 '11 at 2:56
  • 2
    $\begingroup$ If you're looking into computability and randomness, then I supposed you know about the book of Andre Nies. I also highly recommend Alex Simpson's paper "Measure, Randomness and Sublocales". It may not be obvious from the way the paper is written, but his work is relevant for computability in randomness. $\endgroup$ – Andrej Bauer Dec 3 '11 at 22:42
  • $\begingroup$ Yes, most of the things I know on randomness, I know them from Nies book. Thanks a lot for your other reference $\endgroup$ – Archimondain Dec 5 '11 at 12:50

Look at the paper of Cockett and Hofstra on Turing categories.

| cite | improve this answer | |

Without certain additional assumptions, the two characterizations of computability in topological spaces are not equivalent also in the case when uniformity is required in the second characterization. Indeed, the following property follows then from computability in the second sense: a partial recursive function $\iota$ exists such that, whenever $O$ is a basic open set of $Y$, $j$ is an index of $O$ in the given surjection of $\mathbb{N}$ onto the basis of $Y$, and $f^{-1}(O)$ is non-empty, then the number $j$ belongs to the domain of $\iota$, and the set with index $\iota(j)$ in the given surjection of $\mathbb{N}$ onto the basis of $X$ is a subset of $f^{-1}(O)$. On the other hand, computability in the first sense can be present without having this property. To construct an example for this, we can proceed as follows. We first construct such a partition of $\mathbb{N}$ into disjoint two-elements sets of the form {$n_0,n_0+1$},{$n_1,n_1+2$},{$n_2,n_2+3$},{$n_3,n_3+4$},$\ldots$ that no recursive function exists whose value at $j$ belongs to {$n_j,n_j+j+1$} for all $j$ in $\mathbb{N}$. Then we take $X=Y=\mathbb{N}$ with the discrete topology, its basis consisting of all singletons in $\mathbb{N}$, but with different surjections of $\mathbb{N}$ onto this basis. For the space $X$, let both numbers $n_i$ and $n_i+i+1$ be indices of the basic set {$i$}, and in the case of $Y$, let $j$ be the only index of {$j$}. Let $f(x)=x$ for all $x$ in $\mathbb{N}$. Then $f$ is computable in the first sense, since, given any enumeration $k_0,k_1,k_2,\ldots$ of the set {$n_x,n_x+x+1$}, we have the equality $x=|k_l-k_{l+1}|-1$, where $l$ is the first $m$ such that $k_m\ne k_{m+1}$. However, $f$ has not the above-formulated property.

For assumptions which guarantee the equivalence of the two characterizations, cf. Theorem 3.3 in M. Korovina's and O. Kudinov's paper "Towards Computability over Effectively Enumerable Topological Spaces", Electron. Notes Theor. Comput. Sci., 221 (2008) 115--125, http://dx.doi.org/10.1016/j.entcs.2008.12.011 (Unfortunately, the formulation of the theorem needs a correction. For the validity of its conclusion some additional assumption is needed. For instance, it is sufficient to add the assumption that $\alpha i$ is empty for some $i$).

Remark. A partition of $\mathbb{N}$ with the properties used in the above counter-example can be made as follows. We take a sequence $k_0,k_1,k_2,\ldots\,$ of natural numbers which is dominated by no recursive function and satisfies $k_{l+1}>k_l+2l+1$ for all $l$ in $\mathbb{N}$. Then we form subsets $C_0,C_1,C_2,\ldots$ of $\mathbb{N}^2$ so that $C_0$ consists of the pairs $(k_l,k_l+2l+1)$ for $l=0,1,2,3,\ldots$, and, for all $r$ in $\mathbb{N}$, $C_{r+1}$ is obtained from $C_r$ by adding a pair $(\bar{n},\bar{m})$ of natural numbers such that $\bar{n}<\bar{m}$ and next three conditions are satisfied:
1. The numbers $\bar{n}$ and $\bar{m}$ occur in no pair from $C_r$.
2. Whenever $(n,m)\in C_r$, the inequality $\bar{m}-\bar{n}\ne m-n$ holds.
3. If $r$ is even then $\bar{n}$ is the least natural number which occurs in no pair from $C_r$, otherwise $\bar{m}-\bar{n}$ is the least positive integer different from all differences $m-n$, where $(n,m)\in C_r$.
Let $C$ be the union of the sets $C_0,C_1,C_2,\ldots$ Then, for any $j$ in $\mathbb{N}$, exactly one pair $(n,m)$ in $C$ exists such that $m-n=j+1$. We set $n_j=n$ for this pair.

| cite | improve this answer | |

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.