2 votes 2 votes If a problem is undecidable then can we say the problem is either recognizable or unrecognizable Theory of Computation theory-of-computation decidability + – student2018 asked Apr 16, 2017 student2018 1.6k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes No. It can be recognizable (those whose language is recursively enumerable but not recursive) or unrecognizable (those whose language is not even recursively enumerable). Arjun answered Apr 16, 2017 Arjun comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Arjun commented Apr 16, 2017 reply Follow Share Decidability : TM halts(either accepting or rejecting) yes Recognizablity : TM halts on accepting only No, it can halt for reject also just that halting for reject may not happen for all cases. Undecidablity : which is not decidable it means TM doesn't halt or halts only by accepting This means TM does not halt for some inputs (either accepting or rejecting) Unrecognizablity : which is not recognizable it means TM doesn't halt This means TM does not halt for some accepting inputs. (Stronger condition than for the above one). 2 votes 2 votes amrendra pal commented Aug 20, 2017 reply Follow Share sir, is any difference between Turing unrecognizable languages and Turing co-recognizable languages or both same ? 0 votes 0 votes roh commented Jul 16, 2020 reply Follow Share The intersection of a recognizable language and an unrecognizable language is always unrecognizable. Is this statement correct as per the above definitions? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Undecidability only means "Not REC" now ask yourself does 'Not REC' mean RE ? or not even RE. Answer it with 'Anything Possible' and here you got it. Rupendra Choudhary answered May 22, 2017 Rupendra Choudhary comment Share Follow See all 0 reply Please log in or register to add a comment.