# Class of the language of Turing machines that loop on at least one input

$L = \{ \langle M \rangle \mid \text{there is at least one input string on which the $$M$$ does not halt} \}$

Here, for a Turing machine $M$, the notation $\langle M \rangle$ denotes an encoding, over some alphabet, of the code of the Turing machine. To which of the following language classes does $L$ belong?

1. Regular.
2. Context-free but not Regular.
3. Recursive but not Context-free.
4. Recursively enumerable but not recursive.
5. Not recursively enumerable.
• since it is given that M doesn't halt(i'm stuck here) if it is just that M "halts on some input x",then it is easy to say that it is regular,non-recusive..but it is given that M doesn't halt. – Harshil Sep 26 '13 at 2:22
• You're missing the point. The language is not the one accepted by $M$, but rather the one accepted by $L$. The question is, how hard is it to tell whether a given Turing machine halts on all inputs? – Yuval Filmus Sep 26 '13 at 4:52

The language $L$ consists of (descriptions of) Turing machines $M$ such that $M$ does not halt on all inputs. In other words, $\langle M \rangle \notin L$ if $M$ halts on all inputs. Can you think of any connection to the halting problem?