14 votes 14 votes State whether the following statements are TRUE or FALSE: The problem as to whether a Turing machine $M$ accepts input $w$ is undecidable. Theory of Computation gate1987 theory-of-computation turing-machine decidability true-false + – makhdoom ghaya asked Nov 9, 2016 • recategorized Apr 22, 2021 by Lakshman Bhaiya makhdoom ghaya 3.9k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 26 votes 26 votes Yes. The problem as to whether a Turing machine $M$ accepts input $w$ is undecidable which is the well known Halting Problem. If string $w$ is going to loop then we can not determine if it will be eventually accepted by TM or not. Prashant. answered Nov 9, 2016 • edited Jun 15, 2018 by Milicevic3306 Prashant. comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Ayush Upadhyaya commented Feb 18, 2019 reply Follow Share If the halting problem were decidable, then every recursively enumerable language would have been recursive. 6 votes 6 votes Gupta731 commented Aug 31, 2020 reply Follow Share The halting problem and the membership problem for Recursively enumerable languages are nearly identical. The only difference is that in the halting problem we do not distinguish between halting in a final state and non-final state, whereas in the membership problem we do. 2 votes 2 votes Pranavpurkar commented Oct 27, 2022 reply Follow Share This is not the halting problem of turing machine as it clearly mentions “accept” which is only possible when halting is on the final state and thus it is a membership problem. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes yes,string belongs to turing machine or not is undecidable. Tushar Garg answered Mar 15, 2018 Tushar Garg comment Share Follow See all 0 reply Please log in or register to add a comment.