0
$\begingroup$

$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.
Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Harshil
    Sep 26 '13 at 2:22
  • $\begingroup$ 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? $\endgroup$
    – Yuval Filmus
    Sep 26 '13 at 4:52
1
$\begingroup$

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?

Improve this answer
$\endgroup$
5
  • $\begingroup$ i don't think any connection to halting problem $\endgroup$
    – Harshil
    Sep 26 '13 at 2:58
  • $\begingroup$ can u please elabroate ur answer i didn't get it!! $\endgroup$
    – Harshil
    Sep 26 '13 at 2:59
  • $\begingroup$ This is not an answer, but rather a hint. You will have to take it from here on your own. $\endgroup$
    – Yuval Filmus
    Sep 26 '13 at 4:01
  • $\begingroup$ for ur inteligency..._/\ _.... $\endgroup$
    – Harshil
    Sep 26 '13 at 4:41
  • $\begingroup$ @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? $\endgroup$
    – David Richerby
    Sep 26 '13 at 12:47

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.