Question on another GRE Comp Sci problem (Turing Machine stuff...)



I have downloaded the official GRE CS problem at
http://ftp.ets.org/pub/gre/CompSci.pdf and try to solve it. The
following problem is rather tough to deal with.

----

47. Let M be a single-tape, deterministic Turing machine 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
below 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 M prints a 1 at
some point after the nth step.
III. M scans at least n distinct tape squares during the computation C.

----

My guess was 'all these three are decidable'; however, the answer is 'I
and III are decidable while II is undecidable.' Maybe my understanding
on TM is quite sloppy, but I cannot understand why 'M prints a 1 at
some point after n-th step' makes such a glaring difference. I
appreciate any input.

Thanks.

.



Relevant Pages