-1
$\begingroup$

Prove each languages decidable or undecidable.

{ <M> | L(M) is not recognizable}

I am not able to understand how this works. And what is recognizable language? What are the angle brackets? And of course how is language undecidable?

$\endgroup$
4
  • $\begingroup$ (1) a language $L$ is recognizable if there is a Turing machine that accepts all and only the strings in $L$. (2) The notation $\langle\,M\,\rangle$ refers to the description of a TM $M$. Think of it as providing all the information about $M$ that would be necessary for another TM to simulate the running of $M$. (3) A language $L$ is decidable if there is a TM that halts and accepts every string in $L$ and halts and rejects every string not in $L$. To say that a language is undecidable is to say that there is no such TM. $\endgroup$ Feb 3 '16 at 14:12
  • 2
    $\begingroup$ There is really no use for us to repeat common and easily accessed definitions here. Go back to your course material and make an honest attempt at solving the problem on your own. You may also want to check out our reference questions. $\endgroup$
    – Raphael
    Feb 3 '16 at 14:18
  • $\begingroup$ I fairly understand what you are directing me to. I have the solutions to this problem in my text, but I am not able to understand it, which you pointed out, as my basics are not clear enough here. $\endgroup$
    – Rahul Bali
    Feb 3 '16 at 14:20
  • $\begingroup$ In that case, please quote the solution and what specifically you are having trouble with! $\endgroup$
    – Raphael
    Feb 3 '16 at 22:57
4
$\begingroup$

Hint: The language $\{\langle\,M\,\rangle\mid L(M)\text{ is unrecognizable}\}$ is empty (why?) and the empty language is decidable (why?).

$\endgroup$
2
  • $\begingroup$ That's more like the solution I have. What is an empty language? $\endgroup$
    – Rahul Bali
    Feb 3 '16 at 18:59
  • 1
    $\begingroup$ @RahulParashar. A set containing no strings. $\endgroup$ Feb 3 '16 at 19:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.