108 views

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 $n^{th}$ 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

asked | 108 views

I think only I is decidable but given answer is C. How can III be?Can't the TM loop forever without visiting  n distinct tape cells?
answered by Active (4.3k points)
+2
No. Because that will be like making the input tape finite rt? In a finite sized input, there cannot be inifnite distinct configurations possible for the TM.
0
Sir, so infinite no of distinct configuration is only possible if it visits infinite number of distinct tape cells and write non blank tape symbol in them .
0
For third (case III), We can treat M like an LBA with a input tape size n. The key to seeing that this is decidable is to recognize that M in III is being restricted to basically a LBA.

One possible way of deciding would be,
On input <M, n>:
From n, get the possible number of distinct configurations c (finite in this case) of an LBA with i/p of length n. Simulate M for c steps, keeping trck of  no. of distinct i/p symbols that M scans or till the no. of distinct i/p symbols scanned equals n, which ever case comes first. In the latter case, accept. After completion of c steps, if the no. of distinct i/p symbols scanned = n, then accept. Else, reject.

Hope this helps.

1