#Gatebook qno.-23

Question

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  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

Comments

I think only 1st is decidable here... it says computation lasts for atleast n steps i.e We only have to check n length inputs that whether it does any transition n times or not... so we can decide this as if computation ends before n'th step then "no" and if after nth step it's not ended so we can simply say "Yes".

For 2nd we only can say yes if it prints 1 after nth step but what after nth step it goes to infinite loop so we can't say no here ... hence the problem is not decidable.

For 3rd [i assume its computation instead of company], the word "distinct" makes difference we cannot say always say no ...as computation can get stuck in infinite loop. If there was no distinct word here then the problem would be decidable.

So only 1st in decidable.