1
$\begingroup$

A few days ago I had a test that I failed to pass, and it had a question that I failed to do.

This is the question

Let's look at the language $L_\mathrm{loop} = ${ $\left \langle M,w \right \rangle$ | When $M$ is activated on the input $w$, the machine $M$ enters an infinite loop }

We will mark our input length: $|\left \langle M,w \right \rangle| = n$. Determine which of the claims is correct:

  1. The language is in $\mathsf{P}$
  2. The language is not in $\mathsf{NP}$ or $\mathsf{CoNP}$.
  3. The language is in $\mathsf{NP}$ but not in $\mathsf{NPC}$.
  4. The language belongs to $\mathsf{CoNP}$.
  5. None of the above claims are true.

From what I understand in the question, there is a language that accepts Turing machines that go into an endless loop.

  1. It cannot be, if the machine works infinitely, it is impossible to know in polynomial time when we will get yes and when we will get no. It has no algorithm.
  2. Probably can not either. A problem will be in $\mathsf{NP}$ if it has a non-deterministic guessing algorithm. If a witness gives input, it is not possible to say yes to the answer, because it is infinite.
  3. Do not know about it, maybe he is right
  4. Language should belong to $\mathsf{CoNP}$ only when a guessing algorithm should say no. And I do not know if here should be said no and then it's $\mathsf{CoNP}$ or say yes and then it's $\mathsf{NP}$.

I tried to figure out what the answer might be, but I could not figure out the answers to the question.

Maybe 5 is right, because I could not tell everyone else that they were right

$\endgroup$
2
  • $\begingroup$ You are definitely mixing up the languages $L_{loop}$ and the languages $L(M)$ for candidates $M$ that are part of the input of $L_{loop}$. As a hint: What can you say about the decidability (not complexity) of $L_{loop}$? $\endgroup$
    – ttnick
    Jul 21 at 9:57
  • $\begingroup$ I think it is impossible to decide, because it is something that always takes an infinite amount of time $\endgroup$ Jul 21 at 10:14
2
$\begingroup$

From what I understand in the question, there is a language that accepts Turing machines that go into an endless loop.

We do not say a language "accepts" something. Rather the language contains all pairs of turing machines and words, where the TM runs forever (which I take "infinite loop" to mean) on the word.

Also, note that you can define any language, but there doesn't necessarily exist a TM that accepts that language.

$L_{Loop}$ is undecidable because you can reduce the halting problem of a TM $A$ on $w$ to it. Clearly, $\langle A, w \rangle \not\in L_{Loop}$ iff $A$ halts on $w$.

We know that the halting problem is undecidable. If $L_{Loop}$ was decidable, so would be the halting problem. Therefore, $L_{Loop}$ is undecidable, i.e. there exists no algorithm to decide for all words whether they are in the language.

If there's no algorithm, the language can't be in NP, thus 1 and 3 are wrong immediately. As we have just seen, the complement of $L_{Loop}$ is the halting problem, so 4 is wrong too. The rest should be clear.

$\endgroup$
6
  • $\begingroup$ Thank you very much, the language does not belong to np or conp because it is not possible to decide if it does belong and if it does not belong? $\endgroup$ Jul 22 at 13:47
  • 1
    $\begingroup$ The language does not belong to NP, because there exists no turing machine that can for all inputs (= words) decide whether that word is in the language in bounded time. It does not belong to CoNP because its complement language, the language of all $\langle M, w \rangle$ that eventually halt (= not create an infinite loop) is the halting problem, which is also undecidable and therefore not in NP. $\endgroup$
    – idmean
    Jul 22 at 14:36
  • $\begingroup$ I think I understand, because it's a halting problem, and its complication is $ RE $, so 2 is the correct answer. $\endgroup$ Jul 22 at 15:08
  • $\begingroup$ It's the complement of the halting problem. But you're correct otherwise. $\endgroup$
    – idmean
    Jul 22 at 15:09
  • 1
    $\begingroup$ CoNP is the class of languages whose complement is in NP. As we have seen, $L_{Loop}$'s complement is the halting problem, which is not in NP. $\endgroup$
    – idmean
    Jul 22 at 15:26

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.