The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+5 votes
141 views
Consider the following languages
 
L1={<M>∣M is a single tape TM that on any input x does not change the input portion of the tape}
 
L2={<M>∣M is a single tape TM that on any input x does not change any portion of the tape}
 
Which of the following is correct?
 
 
A.) L1 is decidable but L2 is undecidable
 
 
B.) L1 is undecidable but L2 is decidable
 
 
C.) Both L1 and L2 are decidable
 
 
D.) Both L1 and  L2 are undecidable
asked in Theory of Computation by (135 points) | 141 views
I think both $L_{1}$ and $L_{2}$ are nontrivial , so both undecidable .. is it $D$?
An arbitrary Turing machine ever writes something on its input tape is a "Decidable" problem. I am not sure, but these both problems seem to be decidable too until they are asking for a specific letter to be printed.
I think they should be decidable as they are not language property and as @manu00x said it is not focussed about some specific symbols..
If a problem is undecidable we should have some way to get infinite moves in the TM which solves it.
For L2, does not change any portion of the tape. We can look at the transition function of the TM and see whether it is replacing the current symbol with different symbol. So, I think L2 is decidable.
i also think both are decidable, i think we can find above condition by seeing configuration of TM and analyze it in finite time..

@manu00x Any source of the claim that the problem of accepting arbitrary TM printing that ever writes something on input tape is "Decidable Problem"?

Why a proof similar to the problem of accepting TM ever printing a specific letter, is invalid?

Let us replace the transitions that halt the TM with the transitions that halt the TM and write something on input tape, Now, the halting problem of original TM is reduced to this problem. And since, the halting problem is undecidable this problem should be undecidable.

Where I'm going wrong?

Please log in or register to answer this question.



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

28,839 questions
36,693 answers
90,637 comments
34,642 users