edited by
454 views
2 votes
2 votes

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.$
  1. III only
  2. I and III only
  3. II and III only
  4. I, II, and III
edited by

Please log in or register to answer this question.

Answer:

Related questions