3 3 votes Every undecidable language is not recognized by TM ?? Statement is True / False Theory of Computation theory-of-computation + – Magma 855 views answer comment Share Follow Print See all 3 Comments 3 3 Comments reply Kunal Kadian commented Jan 9, 2019 reply Follow flag 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. 0 0 replyShare Shaik Masthan commented Jan 10, 2019 reply Follow flag 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 1 1 replyShare jatin khachane 1 commented Jan 10, 2019 reply Follow flag 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 0 0 replyShare Please log in or register to add a comment.
