[FOM] Practically computable inserparable c.e. sets

[Andrej Bauer]

For pedagocial purposes I would like to implement the computable version
of "Cantor space is homeomorphic to Baire space", i.e., a computable
homeomorphism between the spaces of computable binary sequences and
computable number sequences (all sequences are infinite).

The usual construction of such a homemorphism proceeds by enumeration of
the leaves of a Kleene tree, which in turn is defined using inserparable
c.e. sets (A,B). So, if I want an implementation that will compute
something in the attention span of the students, the inserparable sets
(A,B) have to be chosen carefully. They should be:

(1) easy to compute (both fast and not a lot of code)

(2) smallish numbers should enter A or B quickly, with few numbers
    staying out of both.

(3) smallish numbers should have about equal chances of entering
    A and B.

What are some well known possibilities:

(a) The (Goedel codes of) provable and refutable sentences of a
sufficiently strong theory. This will likely result in a lot of code and
will violate (2) because Goedel numbers of even simplest statements are
rather large and far between. Even if I play with Goedel numberings to
make them dense, there will still be the problem of looking for proofs
and refutations.

(b) Diagonalization against the enumeration of partial computable binary
sequences. Here we would need an enumeration phi_n such that for small
n, phi_n tends to be defined on small arguments and is "random".

(c) There must be tricks from algebra, cellular automata, and the like.
I am hoping someone can suggest something simple. It is not important
how hard it is to prove that the resulting sets (A,B) are inseparable, I
am happy to just refer to a published theorem.

Best regards,

Andrej Bauer