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