15
$\begingroup$

Say $L_1$ and $L_2$ are computable languages. Let $f$ be a function $L_1 \rightarrow L_2$. Let $C$ be the statement, "if $l \subseteq L_2$ and $l$ is a computable language, the preimage $f^{-1}(l)$ is a computable language." Does $C$ imply that $f$ is necessarily a computable function?

$C$ is similar to the topological concept of continuity; a function $g$ between topological spaces is continuous if, for each open set $S$ in the codomain of $g$, $g^{-1}(S)$ is an open set in the domain. Here "open sets" have been replaced with "computable languages." (Computable languages can't actually be considered open sets here, because they aren't closed under infinite union.)

The converse, "$f$ is computable implies $C$," is easily proved. If $f$ is computable, and $l$ is a computable language that's a subset of $L_2$, then let $l' = f^{-1}(l)$. You can computably tell whether something is in $l'$ by first mapping it through $f$ and asking if the result is in $l$. So $l'$ must be a computable language, proving $C$.

$\endgroup$
1
  • 3
    $\begingroup$ The computable languages can be seen as a form of computable topology because they are closed under computable unions. There is a whole area of computable topology which studies these phenomena. $\endgroup$ – Andrej Bauer Nov 10 '20 at 12:21
13
$\begingroup$

Let $L_1 = L_2 = \mathbb{N}$ and let $M \subseteq \mathbb{N}$ be a maximal set and let $L = \mathbb{N} \setminus M$ be its complement. Recall that $L$ is infinite, and that every computably enumerable (c.e.) subset $S \subseteq \mathbb{N}$ contains either finitely many elements of $L$ or all but finitely many elements of $L$.

Let $f : \mathbb{N} \to \mathbb{N}$ be an enumeration of $L$ without repetitions. The map $f$ is not computable, or else $M$ would be a computable subset of $\mathbb{N}$, which a maximal set is not.

We claim that $f$ is a counter-example to your question. Consider any c.e. subset $S \subseteq \mathbb{N}$:

  1. If $S \cap L$ is finite then $f^{-1}(S) = f^{-1}(S \cap L)$ is finite (as $f$ is injective) and therefore a computable set.
  2. If $S \cap L$ contains all but finitely many elements of $L$ then $f^{-1}(S) = f^{-1}(S \cap L)$ contains all but finitely many elements of $\mathbb{N}$, therefore it is a computable set.

In your question you hint at the analogy between computability and continuity. Indeed there is one, but we need to be a bit more sensitive about computability. Let $$\mathcal{E} = \{S \subseteq \mathbb{N} \mid \text{$S$ is c.e.}\}$$ be the set of all c.e. subsets of $\mathbb{N}$, and let $W : \mathbb{N} \to \mathcal{E}$ be a standard enumeration of c.e. sets. We can think of $\mathcal{E}$ as the "computably open" subsets of $\mathbb{N}$. Indeed, they're closed under finite intersections and unions of computable families.

Say that a map $F : \mathcal{E} \to \mathcal{E}$ is computable if there exists a computable $r : \mathbb{N} \to \mathbb{N}$ such that $F(W_n) = W_{r(n)}$ for all $n \in \mathbb{N}$. (This is just the standard notion of computability for numbered sets.)

Your question can be rectified into a theorem like this (I just inserted the emphasized "computable"):

Theorem: A map $f : \mathbb{N} \to \mathbb{N}$ is computable if, and only if, its inverse image map $f^{-1} : \mathcal{P}(\mathbb{N}) \to \mathcal{P}(\mathbb{N})$ restricts to a computable map $f^{-1} : \mathcal{E} \to \mathcal{E}$.

I will leave the (easy) proof as an exercise. The above can easily be generalized from number-theoretic maps to languages.

$\endgroup$
1
  • $\begingroup$ Thanks, I didn't know about maximal or r-maximal sets. I can see how a computable inverse image map could be used to reconstruct $f$, by restricting $f^{-1}$ to singleton sets in its domain and using that to iterate over all the key-value pairs of $f$. And vice versa, obtaining $f^{-1}$ from a computable $f$ by iterating over key-value pairs. It's a little disappointing because I was hoping for a way to get computability for $f$ just from the structure of its domain/codomain. $\endgroup$ – causative Nov 11 '20 at 3:10

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.