Computably enumerable and partial functions

Question

I've been tasked with proving, formally or informally, that these conditions of a language A which is a subset of {0,1}* are equivalent statements.

I must first show that A itself is computably enumerable (c.e). How do I do this somewhat elegantly? According to Wikipedia, I need to show that there basically exists an algorithm that will enumerate {0,1}*. Do I have to come up with an algorithm for a turing machine? I am very confused (our lecture is our only class resource).

Next, I must show there exists a computable partial function that maps {0,1}* to {0,1}* such that A is equal to the domain of that function. Also show that there exists a computable partial function that maps {0,1}* to {0,1}* such that A is the range. Intuitively I could see how this is true, since everything in the domain can be mapped to everything in the range and vice versa, however how do I show that as a commutable partial function? Or that one exists for both instances?

Answer 1

I think you must be misunderstanding the exercise. It would make much more sense if what you're asked to do is

Argue that these three conditions on a language $A\subseteq \{0,1\}^*$ are equivalent:

1. $A$ is c.e.
2. There exists a computable partial function whose domain is $A$.
3. There exists a computable partial function whose range is $A$.

That is, you're not asked to show that the three conditions are true for any particular language $A$, but that for every possible language $A$ they are either all true or all false.

Such equivalences are usually proved by showing a cycle of implications, so you can either do $1\Rightarrow 2$ and $2\Rightarrow 3$ and $3\Rightarrow 1$, or $2\Rightarrow 1$ and $3\Rightarrow 2$ and $1\Rightarrow 3$. Sometimes it is also easier to do, for example, $1\Rightarrow 2$ and $2\Rightarrow 1$ and $2\Rightarrow 3$ and $3\Rightarrow 2$; that depends on which constructions you can come up with most easily.

If your course has defined "c.e." and "computable partial function" via Turing machines, then in principle you need to come up with a Turing machine for each direction of the equivalence -- e.g., for $1\Rightarrow 2$ you assume that there's a Turing machine that enumerates $A$ and must argue that you can make a Turing machine that halts on exactly $A$.

Note that the "domain" of a computable partial function is not (as in mathematics in general) what you define it to be, but exactly the set of those inputs that the Turing machine that computes it halts on.

It will vary greatly with your setting how much handwaving you can get away with during each of these constructions. Only in the most rigidly bare-bones settings will you have to describe the actual transition table for the Turing machine you're trying to construct. If you're in a computer science context, you will often be able to get away with "I can write a program that does such-and-such, and we know that every program corresponds to a Turing machine, therefore a Turing machine that does such-and-such must exist". The "formally or informally" seems to indicate that an argument at this level will be sufficient.