1 votes 1 votes Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False) Theory of Computation decidability recursive-and-recursively-enumerable-languages theory-of-computation turing-machine rice-theorem + – gmrishikumar asked Dec 10, 2018 gmrishikumar 1.7k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Gupta731 commented Dec 10, 2018 reply Follow Share The halting problem is recursively enumerable but not recursive. A similar argument can be used to show that many practical problems associated with software verification are undecidable. For example, the problem of determining whether a program will ever go into an infinite loop is undecidable. 1 votes 1 votes Ram Swaroop commented Dec 16, 2018 reply Follow Share True 0 votes 0 votes Please log in or register to add a comment.
Best answer 5 votes 5 votes False. The TM will definitely halt since it accepts recursive languages. Therefore the problem is decidable. gmrishikumar answered Dec 16, 2018 gmrishikumar comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes FALSE recursive languages are recognised by halting turing machine so , telling whether the TM accepting recursive languge will halt or not is decidable. rballiwal answered Dec 16, 2018 rballiwal comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Halting problem is undecidable for RE languages. But in question its mentioned for recursive. Here for all strings, either they will be accepted or rejected and then always halt. Hence its decidable. So the statement is false. rish1602 answered Jun 28, 2021 rish1602 comment Share Follow See all 0 reply Please log in or register to add a comment.