# 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

## 1 Answer

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?

• i don't think any connection to halting problem – Harshil Sep 26 '13 at 2:58
• can u please elabroate ur answer i didn't get it!! – Harshil Sep 26 '13 at 2:59
• This is not an answer, but rather a hint. You will have to take it from here on your own. – Yuval Filmus Sep 26 '13 at 4:01
• for ur inteligency..._/\ _.... – Harshil Sep 26 '13 at 4:41
• @user561298 The language is defined in terms of whether Turing machines halt or not. Are you sure there's no connection with the halting problem? – David Richerby Sep 26 '13 at 12:47