search
Log In
0 votes
384 views
Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)
in Theory of Computation 384 views
1
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.
0
True

2 Answers

3 votes
 
Best answer
False.

The TM will definitely halt since it accepts recursive languages. Therefore the problem is decidable.
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.

Related questions

6 votes
2 answers
1
1.8k views
My Question $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$ I have to check that it is Turing Recognizable or not (i.e R.E) My Approach/Doubt Question taken from https://gateoverflow.in/7427/which-following ... $100$ $T_{yes}\subset T_{no}$. Hence it is not RE.But in the solution it is R.E.
asked Sep 9, 2017 in Theory of Computation sourav. 1.8k views
4 votes
2 answers
2
806 views
Since Recursive languages are closed under intersection, therefore it decidable. Am I wrong?
asked Jan 18, 2018 in Theory of Computation nikhil_cs 806 views
3 votes
2 answers
3
5 votes
1 answer
4
461 views
Which of the following is not a recursive language? a. Regular language b. {$\langle M,w \rangle$ | $M$ is a DFA that accepts $w$} c. {$\langle M \rangle$ | $M$ is a TM and there exists an input which halts within $100$ steps} d. {$\langle M \rangle$ | $M$ is a TM and $L(M)$ is regular }
asked Sep 11, 2015 in Theory of Computation Shefali 461 views
...