Is it possible to put a topology on Turing-recognizable languages to express density among all the languages?

Question

In a Calculability and complexity course I had at univeristy, we proved that there exist languages that are not Turing-recognizable basiclly using Cantor's diagonal argument (the set of all languages is uncountable and the set of Turing-recognizable languages is countable). This immediately brought the analogy with $\mathbb Q$ which is countable inside $\mathbb R$ which is not. But we have a topology on $\mathbb R$ (and thus on $\mathbb Q$) which allows us to show that $\mathbb Q$ is a dense subset of $\mathbb R$ (also it's a metric space).

A question then popped in my head: is there any way to put a topology onto the set of languages that would lead to a smilar result, i.e. density of the Turing-recognizable lanuages among all the languages?

Note that I have no idea if this even makes sense: I'm not really into theoretical computing, and I have no idea if the notion of "closeness" between languages makes any sense. This is just a question I've hold for too long now and I had to ask if somebody already answered this or if this is just a pointless question.

Answer 1

From a slightly different perspective: for theoretical purposes it's often better to work with computable and uncomputable sets rather than languages; indeed, if your language is over a finite alphabet $A$, then there's the classic natural correspondance between $A^*$ and $\mathbb{N}$ given by 'base-$|A|$ representation', and it shouldn't be hard to convince yourself that a language $\mathcal{L}\subseteq\mathcal{P}(A^*)$ is Turing recognizable iff the set $S_L\subseteq\mathbb{N}$ given by the correspondence is computable.

This lets us use a standard topology on subsets of $\mathbb{N}$; for instance, we can use a metric like $d(A,B)=2^{-n}$, where $n$ is the smallest element of $A\Delta B$. Under this topology, the computable sets are indeed 'dense' in the set of all subsets of $\mathbb{N}$ — in fact, the finite sets (all of which are computable) are already dense. (This is exactly analagous to the dyadic rationals being dense in the set of reals, although the 'natural' mapping $S\subseteq\mathbb{N}\mapsto \sum_{s\in S} 2^{-s}$ to map the subsets of the naturals into $[0,1]$ doesn't quite work since it's not 1-to-1.)

Answer 2

I don’t know if this can be done as you want, but some thoughts: a language over some fixed alphabet $\Sigma$, is just a set of (finite length) strings, so a member of $\mathscr{P}(\Sigma^\ast)$. $\Sigma^\ast$ is essentially a subset of a product $\Sigma^\omega$ so can be given a somewhat natural topology (if the finite set $\Sigma$ gets the discrete topology; we get a subset of a Cantor set, topologically).

The power set of $\Sigma^\ast$ can be given a product topology again, using the characteristic function identification. It is well-known that this set indeed has a countable dense subset (Hewitt-Marzcewksi-Pondizcery theorem) so I think there is good hope we can find a Turing-recognisable family of languages that is dense in this topology as described. No time to look into further details as of yet.. Looks like a nice exercise for someone, though.