GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
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
asked in Theory of Computation by (133 points)   | 135 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.



Top Users Sep 2017
  1. Habibkhan

    8586 Points

  2. rishu_darkshadow

    3046 Points

  3. Warrior

    2862 Points

  4. Arjun

    2796 Points

  5. A_i_$_h

    2546 Points

  6. manu00x

    2116 Points

  7. nikunj

    1990 Points

  8. Bikram

    1874 Points

  9. makhdoom ghaya

    1820 Points

  10. SiddharthMahapatra

    1718 Points


26,301 questions
33,864 answers
80,437 comments
31,203 users