Are all continuous functions computable (for a peculiar definition of continuity)? A (partial) function $f:\mathbb{N}\rightarrow\mathbb{N}$ is continuous if, for every recursively enumerable (henceforth, $RE$) set $S$, the preimage $f^{-1}(S)=\{x\in\mathbb{N}\mid f(x)\in S\}$ is also $RE$. This isn't a standard definition of continuity - although it is very obviously inspired by the topological definition - and is what we referred to in the title as being peculiar.
A (partial) function $f:\mathbb{N}\rightarrow\mathbb{N}$ is computable if it can be realized in some Turing-complete model of computation (for example, if there exists a Turing machine s.t., with input $n$, halts with $f(n)$ as the result, or loops forever if $f$ is not defined for the input).
It is a simple exercise to check that every computable function is continuous (given a computable function $f$ and a $RE$ set $S$, one can enumerate the preimage by simply enumerating all naturals $n$, computing $f(n)$ and checking whether $f(n)\in S$ or not), but what about the converse? Given any  continuous function, is it possible to show that it is also computable?
I believe there should be a simple cardinality argument that answers the question in the negative, but i haven't been able to formulate it. A concrete example would be preferred, of course, but beggars can't be choosers.
 A: Your suspicion is right - continuity in your sense, which I'll call "ce-continuity" to avoid confusion, does not imply computability. For example, we have the following:

There is a total injective function $f:\mathbb{N}\rightarrow\mathbb{N}$ such that for every c.e. $X$ either $f^{-1}(X)$ is finite or $f^{-1}(X)$ is cofinite.

Call such a function "wild." Every wild function is trivially ce-continuous, but no such function can be computable. This is because if $f$ were wild and computable, the set $E=\{f(2n):n\in\mathbb{N}\}$ would have to be c.e., but $E$ has bi-infinite $f$-preimage.
One way to construct a wild function is to first construct a cohesive set: a set $X\subseteq\mathbb{N}$ is cohesive iff $X$ is infinite and for every c.e. set $A$, either $X\cap A$ is finite or $X\cap(\mathbb{N}\setminus A)$ is finite. That is, a cohesive set either "mostly lies in" or "mostly avoids" each c.e. set. It's a good exercise to show that if $X$ is cohesive then the principal function of $X$ (= send $n$ to the $n$th element of $X$ in increasing order) is wild. Here's a sketch of how to construct a cohesive set; filling in the details is a good exercise:
Let $(W_e)_{e\in\mathbb{N}}$ be some enumeration of the c.e. sets. Define new sets $A_e$ recursively as follows: we let $$A_e=(\bigcap_{i<e}A_i)\cap W_e$$ if that intersection is infinite and let $$A_e=(\bigcap_{i<e}A_i)\setminus W_e$$ otherwise. It's easy to check that $A_0\supseteq A_1\supseteq ...$ and that each $A_e$ is infinite. Now we can't just take the intersection of the $A_i$s since that might be finite (or even empty!), but we can do something "intersection-flavored:" recursively let $a_e$ be the least element of $A_e$ greater than every $a_i$ with $i<e$ (this is well-defined since the $A_e$s are infinite). The set $$X=\{a_e:e\in\mathbb{N}\}$$ can then be shown to be cohesive. If you've seen the notion of diagonal intersections in set theory, this is a similar idea.

One way we can strengthen ce-continuity is by adding a uniformity assumption: say that a (total, for simplicity) function $f:\mathbb{N}\rightarrow\mathbb{N}$ is uniformly ce-continuous iff there is some computable function $h$ such that for each $e$ we have $f^{-1}(W_e)=W_{h(e)}$. Clearly every uniformly ce-continuous function is ce-continuous and every computable function is uniformly ce-continuous, so this is genuinely a good refinement of the original notion.
Once we make this modification, we do in fact "close the gap:" the uniformly ce-continuous functions are exactly the computable functions. To see this, suppose $f$ is uniformly ce-continuous via $h$ and we want to compute $f(n)$. In parallel we'll enumerate each $W_{h(i)}$; eventually for some $i$ we see $n$ enter $W_{h(i)}$, and at that point we know that $f(n)=i$.
In general, there are lots of seemingly-nice notions which are actually pretty badly behaved until we add a uniformity condition to them.
