202 views
0 votes
0 votes
Let M0, M1, M2,..., be an effective enumeration of all Turing machines. Which of the following problems is (are) decidable ?

I. Given a natural number n, does Mn starting with an empty tape halt in fewer than n steps?

II.Given a natural number n, does Mn starting with an empty tape halt after at least n steps?

(A). I only

(B). II only

(C). Both I and II

(D). Neither I nor II

Please log in or register to answer this question.

Related questions

4 votes
4 votes
3 answers
1
smartmeet asked Feb 7, 2017
777 views
Given TMs and L = {x/Every halts on input x } which of the following is true about L?(A) L is recursively enumerable but not recursive(B) L is Recursive but not Context...
3 votes
3 votes
2 answers
3
Shreya Roy asked Nov 18, 2016
1,008 views
Let L = {xy | xwy L1, |x| = |w| = |y|}. Then L is(L1 is regular)(A). Regular(B). Non regular(C). May be regular(D). None