Test by Bikram | Mock GATE | Test 4 | Question: 35

Question

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?

1.   The computation $C_i$ lasts for at least $k$ steps.
2.   The computation $C_i$ lasts for at least $k$ steps, and $DM$ prints $1$ at some point after the $k^{th}$ step.
3.   $DM$ scans at least $k$ distinct tape squares during the computation $C_i.$

• A. III only
• B. I and III only
• C. II and III only
• D. I, II, and III

Comments

Ask yourself, "What if the computation Ci lasts for at least k steps, and from the next step onwards the DM keeps on printing 0's endlessly?" Can you say that it will (or will not) print a 1 some time? You can stop if it prints 1 and say yes, but what if it never prints 1? What if it keeps printing 0's forever?

---

II is undecidable because we don't know whether it will print 1 after k steps or not. that is why it is undecidable ...

---

Okay, so I get why $III$ is decidable now. Check out Arjun's comment on the answer to this question.