The Gateway to Computer Science Excellence
0 votes
Let $X = \{\langle M, w \rangle \mid  \text{M is a single-tape TM that never modifies the portion of the tape that contains the input $w$ } \}$

Is $X$ decidable? Prove your answer.
in Theory of Computation by Veteran (60.8k points) | 76 views

1 Answer

0 votes
As we know, it is undecidable whether a string belong to the language accepted by a particular turing machine or not [Membership problem of Turing Machine]. So, How can it, in the first place, recognise whether some sub-string 'w' is a part of given input string 's'(say) or not. Only after it recognises whether substring 'w' is a part of string "s" which belongs to language accepted by it (i.e. whether it is present on tape or not) it can decide whether to write on that part or not.

So to conclude the answer to this question should be "it is undecidable"
by (23 points)

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
50,834 questions
57,853 answers
108,392 users