The languages $A, B \in \Sigma^*$ are two semi-decidable but not decidable languages. Show that $A \cup B$ is semi-decidable.
If a language is semi-decidable then it is also recursively enumerable. And vice-verse. Therefore, if I can show that $A \cup B$ is recursively enumerable, then it is also semi-decidable. A recursively enumerable language must be total and computable. Here is my attempt:
We define the following sets: $$f_A(\mathbb{N}) = \{f_A(0), f_A(1),f_A(2),...\}$$ $$f_B(\mathbb{N}) = \{f_B(0), f_B(1),f_B(2),...\}$$ $$f_{A \cup B}(\mathbb{N}) = A \cup B = ...$$
The problem here could be that the number of words in $A$ might be infinite, therefore you would never actually start enumerating $B$. The solution would thus be to alternatively enumerate elements from both sets, like the following:
$$f_{A \cup B}(\mathbb{N}) = A \cup B = \{f_A(0), f_B(0),f_A(1),f_B(1),...\}$$
A more formal definition: $$ f_{A \cup B}(n) = \begin{cases} f_A\left({\frac{n}{2}}\right) & n \ \text{is even,} \\ f_B\left({\frac{n-1}{2}}\right) & n \ \text{is uneven} \end{cases} $$
Here, $n$ is the position of the words in the set $A \cup B$, starting from $n=0$. Now we must show that $f_{A \cup B}$ is a total and computable function. The function is computable because:
- We know that determining whether a number is even or odd is computable.
- This means that $\frac{n}{2}$ and $\frac{n-1}{2}$ are also computable.
- $A$ and $B$ are semi-decidable and therefore, $f_A$ and $f_B$ are also computable because there exists $f_A(\mathbb{N})$ and $f_B(\mathbb{N})$ that recursively enumerate $A$ and $B$.
Therefore, $f_{A \cup B} $ is computable. The function is total because:
- There exists a lower and upper bound.
- $f_A$ and $f_B$ are total.
Therefore, we have shown that $f_{A \cup B}$ is computable and total thus is recursively enumerable. It follows from the equivalence that $f_{A \cup B}$ is semi-decidable.
I'm a little unsure if my explanation for totality is adequate enough for this. How can I improve it?
I am first going to provide some definitions in the context of Turing machines, which I am going to use later.
Let us first say that the collection of strings that a Turing machine $M$ accepts is called the language of $M$, or the language recognized by $M$, and let us denote this lanugage by $L(M)$.
Def. 1: A language is called Turing-recognizable (or recursively enumerable) if some Turing machine recognizes it. We also call such a language semi-decidable.
A Turing machine has three potential outcomes: accept, reject, or loop. A loop means that our Turing machine does not halt. A Turing machine that halts on all inputs is called a decider. We say that a Turing machine, which is a decider and recognizes a given language, decides that language. Consequently, every decidable language is also semi-decidable.
Why is a semi-decidable language also called recursively enumerable in the first place? There is a special type of Turing machine called enumerator. It starts with a blank input on its tape and outputs all the strings for its language (possibly with repition). It may print an infinite list of strings, if it does not halt.
Theorem 1: A language is semi-decidable (Turing-recognizable) if and only if some enumerator enumerates it.
Def. 3: A (total) function $f: \Sigma^* \to \Sigma^*$ is computable if there is a Turing machine $M$ that halts on every input $\omega$ with $f(\omega)$ as its output on the tape.
And we say that a set enumerated by some enumerator is said to be recursively enumerable. Hence, building a computable function which recursively enumerates the given set is sufficient.
Now, the nice thing about your proof is, that your function alternates the elements of the sets $A$ and $B$. This is essentially the same as constructing a $2$-tape Turing machine simulating a Turing machine $M_1$ recognizing $L_1$ on the first tape and a Turing machine $M_2$ recognizing $L_2$ on the second tape. And since $M_1$ or $M_2$ could run forever, we must alternate this process!
To see this more clearly, I am going to provide a proof using Turing machines.
We know that a language is semi-decidable if there exists a Turing machine that recognizes it (by definition $1$). Since our theorem states that the union of two such languages is also semi-decidable, it is sufficient if we explicitly construct a Turing machine which recognizes such a union.
Theorem 2: Given two semi-decidable languages $L_1$ and $L_2$. Then $L_1 \cup L_2$ is semi-decidable.
Proof: Let $M_1, M_2$ be Turing machines recognizing $L_1$ and $L_2$, respectively. We will construct $M_{L_1 \cup L_2}$ which recognizes $L_1 \cup L_2$ using $2$-tapes as follows: copy each input $\omega$ from tape one to tape two and position both heads at the start of the tapes. Simulate $M_1$ on the first tape and $M_2$ on the second tape. Simulate the first step of $M_1$, then simulate the first step on $M_2$, and so on. If either $M_1$ or $M_2$ accepts $\omega$, we know that $\omega \in L_1 \lor \omega \in L_2$, hence we let $M_{L_1 \cup L_2}$ accept; otherwise we run forever since $M_1$ and $M_2$ do not halt, hence $\omega \notin L_1 \land \omega \notin L_2$. Hence, $M_{L_1 \cup L_2}$ recognizes $L_1 \cup L_2$, and therefore $L_1 \cup L_2$ is semi-decidable.
(Notice that you can apply nearly the same to the intersection of two semi-decidable languages.)
I like your proof, however, I think that constructing a Turing machine directly is more satisfying, since we do not need any assumptions other than the definition of "semi-decidable" and the ones given in the theorem itself. Just show that there is a Turing machine that accepts the given language, and we are done.
Your proof on the other hand needs some more (of course somewhat trivial) knowledge in the given context. The things I have also stumbeled upon are mentioned in the comments by Kolmin and Manlio. $f_A$ and $f_B$ are total and computable of course, because they recursively enumerate $A$ and $B$ by assumption, but I would state that much earlier in your proof.
You say
This information is already given by assumption, so I would suggest to state these fact right at the beginning by saying something like "$A$ and $B$ are semi-decidable by assumption, hence there exist computable (total) functions $f_A$ and $f_B$ that recursively enumerate $A$ and $B$, respectively."
Saying that these enumerations could be infinite is good (that is the key idea of the proof)! Now, just state that we construct a third function using $f_A$ and $f_B$ and provide a way of dealing with this infinite case. And that is precisely what you did. As Manlio already stated, the boundedness is irrelevant. Then concluding that $f_{A \cup B}$ is total is an imediate consequence of the definition of $f_A$ and $f_B$.
Please notice that what I have said might be nitpicky since your proof is already correct, but I think that it can be improved by the small details that I've provided.