Complexity of the language that enters an infinite loop

Question

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

Answer 1

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.