0 0 votes Is Halting Problem in Turing Machine is partially decidable or not even partially decidable? Theory of Computation + – dharmik_3103 319 views answer comment Share Follow Print See 1 comment 1 1 comment reply Shaik Masthan commented Dec 13, 2024 reply Follow flag Whenever you get such doubt, you just need to ask yourself that, can I get output "yes" for "yes" case ? If so, it must be atleast partially decidable. In this case, as halting problem - halt for the strings in the language - producing yes for yes case. Therefore it is atleast partially decidable. Further, I recommend to watch GO classes free lectures available on this topic in youtube. 0 0 replyShare Please log in or register to add a comment.
Best answer 1 1 vote Halting problem is indeed partially decidable. This is because Halting Problem is Resursively Enumerable (but not recursive). Refer - https://www.geeksforgeeks.org/decidability-and-undecidability-in-toc/ https://gateoverflow.in/748/gate-cse-2001-question-7 https://cs.stackexchange.com/questions/133366/how-to-show-a-language-is-partially-decidable mv_ind answered Dec 13, 2024 • selected Dec 13, 2024 by Shaik Masthan mv_ind comment Share Follow 0 reply Please log in or register to add a comment.
