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.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+2 votes

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 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

0 votes

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?

+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.

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.

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 487
- Exam Queries 436
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,194 questions

43,647 answers

124,088 comments

42,929 users