566 views
4 votes
4 votes

Let M be a single-tape deterministic TM with tape alphabet { blank, 0, 1 }, and let C denote the

( possibly infinite ) computation of M starting with a blank tape. The input to each problem is M, 

together with a positive integer n. Which of the following problems is(are) decidable ?

I.  The computation C lasts for at least n steps

II. The computation C lasts for at least n steps, and prints 1 at some point after n^{th} step

III. M scans at least n distinct tape cells during the company C

(A). III only

(B). I and II only

(C).I and III only

(D).I,II and III

1 Answer

0 votes
0 votes
I think only I is decidable but given answer is C. How can III be?Can't the TM loop forever without visiting  n distinct tape cells?

Related questions

4 votes
4 votes
3 answers
1
smartmeet asked Feb 7, 2017
782 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
4
Shreya Roy asked Nov 18, 2016
1,014 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