3
$\begingroup$

Let $G = \{\langle M_1\rangle, \langle M_2\rangle, \langle M_3\rangle,\cdots\}$ be an infinite turing recognizable language, whose members are descriptions of turing machines.

How can one prove that the union of all the languages recognized by the turing machines in $G$, $L(M_1) \cup L(M_2) \cup L(M_3)\cup\cdots $ is turing recognizable?

I tried to prove it by building an enumerator for the language, using the fact that since $G$ is turing recognizable it can be produced by one.

E' = 
1. Initialize steps counter i=0
2. Run E, the enumerator of G, number of steps equal to i.
3. For every turing machine description M produced by E:
   3.1 for every input word corresponding to 0 up to i according to lexicographic order do:
      3.1.1 Run M on the current input.
      3.1.2 print if M accepts.
4. increase i by 1, and go back to step 2.

Is this a correct approach? Running the enumerator for a limited amount of steps would produce the same words over and over again. Is this not a problem when creating an enumerator? Is $E'$ valid and producing the language as needed? If not, what should be changed?

Improve this question
$\endgroup$
4
  • $\begingroup$ You write $G$ as ({<M_1>, <M_2>, <M_3> ...}), what does the outermost parentheses mean? And what is T? $\endgroup$
    – xskxzr
    Jun 29, 2019 at 3:56
  • $\begingroup$ @David Richerby From my experience it is sometimes considered rude to post a question without adding your own effort to solve it. Therefore I added it, presumably that it does not stand as a full and valid solution. I could delete my work on solving it if necessary $\endgroup$
    – user99674
    Jun 29, 2019 at 8:39
  • $\begingroup$ @xskxzr Sorry for the confusion, I hope it's okay now $\endgroup$
    – user99674
    Jun 29, 2019 at 8:40
  • $\begingroup$ @S.Peter Sure, it's good to include what you've managed, but your original question was just "Please check my work". Now that you have specific questions about your solution, the question is much better and may be useful to other people in the future. Thanks! $\endgroup$
    – David Richerby
    Jun 29, 2019 at 11:24

1 Answer 1

Reset to default
0
$\begingroup$

Your enumerator is incorrect. Because there are infinitely many Turing machine descriptions in $G$, the loop corresponding to Line 3 will not halt, so i will never be increased. Also, Line 3.2 may not halt too.

The correct enumerator is:

E' = 
for i = 1 to infinity:
    Run E, the enumerator of G, to get the ith description of Turing machine <Mi>
    Build an enumerator Ei for Mi 
    for j = 1 to i - 1:
        Run Ej to get the ith string, print it
    Run Ei to get the first i strings, print them

Suppose $E_i$ prints $s_{i1},s_{i2},\ldots$ in order. Then after $i$ iterations, $E'$ would have printed $s_{11},\ldots,s_{1i},s_{21},\ldots,s_{2i},\ldots,s_{i1},\ldots,s_{ii}$ (note this is not the order they are printed), and would print $s_{1(i+1)},s_{2(i+1)},\ldots,s_{i(i+1)},s_{(i+1)1},\ldots,s_{(i+1)(i+1)}$ in order in the $(i+1)$th iteration. Of course, before printing a string, you can check if it has been printed to avoid duplicates.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.