recategorized by
3,881 views

2 Answers

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.
edited by
Answer:

Related questions

14 votes
14 votes
4 answers
1
makhdoom ghaya asked Nov 9, 2016
3,493 views
State whether the following statement are TRUE or FALSE.$A$ is recursive if both $A$ and its complement are accepted by Turing machines.
21 votes
21 votes
4 answers
2
makhdoom ghaya asked Nov 9, 2016
3,286 views
State whether the following statements are TRUE or FALSE:The intersection of two CFL's is also a CFL.
13 votes
13 votes
2 answers
3
makhdoom ghaya asked Nov 9, 2016
2,462 views
State whether the following statements are TRUE or FALSE:All subsets of regular sets are regular.
17 votes
17 votes
5 answers
4
makhdoom ghaya asked Nov 9, 2016
3,616 views
State whether the following statements are TRUE or FALSE:Regularity is preserved under the operation of string reversal.