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


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

36,194 questions
43,647 answers
124,088 comments
42,929 users