I got stuck on this question while studying for final exam.

the language

I thought about reducing L' to L to prove that L' is recognizable since L is recognizable. I am not 100% sure if that is correct.

  • 2
    $\begingroup$ If you would type in the text here (using LaTeX), I bet people would be more inclined to help you. One hint: did you try coming up with a machine that recognizes $L'$? What could such a machine do? (Ps, you don't have to be clever, often a brute force attempt works!) $\endgroup$
    – Pål GD
    Apr 18 '13 at 23:21
  • 3
    $\begingroup$ We first begin by creating a recognizer for L', we'll name it R. We then run R by running each Turing machine M on input x and if one of them accepts, we accept. Otherwise we reject/loop forever. $\endgroup$
    – sPaz
    Apr 18 '13 at 23:30
  • $\begingroup$ @PålGD, just remember this is theory, i.e., the easy stuff. Doing something efficiently, that is the hard work. ;-) $\endgroup$
    – vonbrand
    Apr 18 '13 at 23:38

sPaz, your answer in the comment is on the right track.

I'll give you some more hints.

  1. Since $L$ is RE, as you said, we have a TM that accepts it. Let's call it $R$.
  2. Now, we can run $M_i$ on $x$ for any $M_i$ that is being accepted by $R$.
  3. The question is, what happens if $M_i$ is not accepted by $R$ (and in fact, $R$ goes into a loop)? Also, what happens if $M_1$ is accepted by $R$, but $M_1$ goes on an infinite loop on input $x$?

The standard technique of "running in parallel" (dovetailing) should help you to complete your proof. In more details:

We have a counter $i$. We run $i$ steps of $R$ on any machine $M_j$ such that $\langle M_j \rangle < i$. We keep a list of all the machines that were accepted by $R$. For each such machine, we run $i$ steps of that machine on $x$. If any of them accepts, we accept. Otherwise, we set $i\leftarrow i+1$ and continue.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.