0
$\begingroup$

If K = {<<M>> | L(M) has at least 1 word}, then does K belong to the class of recursive enumerable (RE) languages or its complement?

I'm a bit confused, because if it is RE, then we'd have a TM W that semidecides it, but even for some language, L(M), that does halt for at least a word, we don't know which word it is and may require a word with length tending to infinity.

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $\{M_n\}$ and $\{W_n\}$ be recursive enumerations of the machines and the words. Now for each $n$ run $M_1\ldots M_n$ on $W_1\ldots W_n$ for $n$ steps, and output the code of the machines that stopped at some point. That produces a recursive enumeration of $K$.

$\endgroup$

Your Answer

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

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