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