0
$\begingroup$

Consider the language $A = \{\langle M\rangle : M$ is a Turing Machine and $| L(M) | = 9\}$. That is, $M$ accepts the language of a set of exactly 9 strings. I want to determine if this language is Turing Recognizable or co-Turing Recognizable or neither.

I think it might be Turing Recognizable considering the construction of the following Turing Machine Below:

  1. On a tape insert each of the accepted strings of $L(M)$ in each cell mod 10. So the concatenation of every cell 1,2,3,...,9 mod 10 would be one of the strings in $L(M)$
  2. Then on any input string $w$, compare each character of $w$ one-by-one based on all the characters in the tape cells so far and write $w$ in the 0 mod 10 cells of the tape
  3. Accept if $w$ matches any of the strings in cells 1,2,3,...,9 mod 10 or reject otherwise

I believe this construction of the Turing Machine above is correct and also is the synthesis of a 10-tape Turing machine. I'm just not sure if this is the correct approach for this question. Can someone please provide me with some feedback if this approach is correct?

I would also like to identify if $B = \{\langle M\rangle : M$ is a Turing Machine and $| L(M)| \geq 9\}$ is Turing Recognizable or co-Turing Recognizable but haven't identified a solid argument as yet since I'm not 100% confident in my argument above.

$\endgroup$
2
  • $\begingroup$ The language is undecidable. Rice's theorem can be used. $\endgroup$
    – pcpthm
    Feb 8 at 8:19
  • $\begingroup$ Can you please explain how Rice's Theorem can be used to show that? $\endgroup$
    – ENV
    Feb 8 at 12:56

1 Answer 1

1
$\begingroup$

The problem with $A$ is that you don't know in advance which $9$ strings to check. There are infinitely many words.

Moreover, intuitively (and only intuitively, this is not a formal argument), if you start checking whether a given machine $M$ accepts strings, even if you try all of them in parallel (in increasing number of steps), you can never know if you'll reach 9, and if you reached 9, you still won't know if you'll reach more.

Thus, the intuition is that $A$ is not going to be neither recognizable nor co-recognizable.

Now, to prove this you'll need to come up with appropriate reductions. A good approach is to try reductions from $A_{TM}$ and $A_{\overline{TM}}$. Try it and let us know if you get stuck.

As for $B$, the reasoning is a bit similar, but here if you ever reach $9$ words that are accepted, you're done. So there is a way to recognize the language (but it's still not co-recognizable).

$\endgroup$
2
  • $\begingroup$ Could you please explain how to further create reductions from $A_{TM}$ and $A_{\overline{TM}}$? Reductions in particular are still pretty new to me. Would I have to suppose there's a decider for $A_{TM}$ and $A_{\overline{TM}}$ and make them then decide $A$ or $B$ provided in my original question? More generally, can you please explain why such reductions would prove TM recognizable or coTM recognizable? $\endgroup$
    – ENV
    Feb 8 at 20:57
  • $\begingroup$ There are many many sources about reductions, both in textbooks and on this website. I think it would be better if you first learn this topic a bit. Showing an example of a reduction on this specific example would only confuse (since it will include both reductions, which are new to you, as well as this specific problem, and it will be hard to separate them). $\endgroup$
    – Shaull
    Feb 8 at 21:25

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.