Let $DM$ be a single-tape, Deterministic Turing machine with tape alphabet $\left \{ blank,0,1 \right \}$, and let $C_i$ denote the (possibly infinite) computation of $DM$ starting with a blank tape.
The input to each problem below is $DM$, together with a positive integer $k$.
Which of the following problems is/are decidable?
- The computation $C_i$ lasts for at least $k$ steps.
- The computation $C_i$ lasts for at least $k$ steps, and $DM$ prints $1$ at some point after the $k^{th}$ step.
- $DM$ scans at least $k$ distinct tape squares during the computation $C_i.$
- III only
- I and III only
- II and III only
- I, II, and III