269 views
Every undecidable language is not recognized by TM  ??

Statement is True / False

I think,

A language is undecidable if there does not exist a halting TM.

A language is not recognised by TM if it is Not REL. i e. Langauages accepted by TM are REL.

Your question boils down to, " Is every undecidable language, also not REL?"

Answer is NO. Bcoz for undecidable languages there exist a TM, though it is not halting, that doesn't matter.
kunal what you said is true, but i want to simplify

accepted means halts, recognizes means not halt

Decidable languages ==> recognized and accepted by TM ===> REC

Semi decidable languages ==> recognized by TM but not accepted ===> RE but not REC

Not even Semi decidable languages ==> not even recognized by TM  ===> NON-RE

Undecidable means = which is not decidable = Semi decidable languages $\cup$ Not even Semi decidable languages
If Undecidable language and is RE then it will be recognized by TM

If it is Non RE then it won't be recognized by TM..so statement is False...there are undecidable languages that can be recognized that are Partially UD

1
60 views
1 vote