# Prove that the Language is Recognizable

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

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.

• 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!) – Pål GD Apr 18 '13 at 23:21
• 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. – sPaz Apr 18 '13 at 23:30
• @PålGD, just remember this is theory, i.e., the easy stuff. Doing something efficiently, that is the hard work. ;-) – vonbrand Apr 18 '13 at 23:38

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$?
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.