0 votes 0 votes How to distinguish between a problem which is (undecidable) and which is (undecidable but partially decidable); or rather for a given problem how to say in which category it falls? Theory of Computation decidability theory-of-computation turing-machine recursive-and-recursively-enumerable-languages + – Mizuki asked Nov 14, 2018 Mizuki 472 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply goxul commented Nov 14, 2018 reply Follow Share You should study Chapters 4 and 5 in Sipser's book on Theory of Computation. It's very well explained. 0 votes 0 votes Mizuki commented Nov 14, 2018 reply Follow Share @goxul Thanks! 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes I have seen your question I am not very sure of the answer,undecidable is sub classified as partially undecidable or semi-decidable,I don't want to confuse you with a wrong answer,Undecidable is when the Turing Machine does not halt so,semi and partial are Halting Turing Machines just for one particular case but not for the entire Grammar.Not very sure but here is what I think.Decidable is when you can make Turing Machine halt for the entire set of Languages generated by the grammar. sripo answered Nov 14, 2018 sripo comment Share Follow See 1 comment See all 1 1 comment reply Mizuki commented Nov 14, 2018 reply Follow Share Thanks! 0 votes 0 votes Please log in or register to add a comment.
