The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+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 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 in Theory of Computation by Active (4.3k points) | 108 views

1 Answer

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?
answered by Active (4.3k points)
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.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,072 questions
49,594 answers
65,788 users