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?

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.

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 .

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.1k
- Engineering Mathematics 4k
- Digital Logic 1.7k
- Programming & DS 3k
- Algorithms 2.6k
- Theory of Computation 3.2k
- Compiler Design 1.2k
- Databases 2.4k
- CO & Architecture 2.1k
- Computer Networks 2.4k
- Non GATE 819
- Others 1.1k
- Admissions 244
- Exam Queries 420
- Tier 1 Placement Questions 16
- Job Queries 39
- Projects 4

29,157 questions

36,985 answers

92,166 comments

34,824 users