Problem Detail: A non-erasing Turing machine is one that cannot replace a symbol with a blank unless the symbol under the read head is a blank. I’m trying to understand whether there is loss of generality because of this restriction. My guess is that there is no loss of generality, because the restriction above merely restricts replacing characters with blanks, but we can just as easily replace them with some other symbol and construct any rules that might have used blanks to use the new symbol. I think that’s too simple a solution though. Can anyone give me any insight as to how to show whether or not generality is lost in the special case of non-erasing Turing machines?
Asked By : Victor Brunell
Answered By : André Souza Lemos
The purpose of the blank symbol is to differentiate the tape alphabet from the language alphabet. It is useful, typically, when you are trying to formulate a decision problem. From a more abstract point of view, as you clearly realize, a machine whose tape alphabet has at least two symbols is still exactly a Turing machine. So you are erring towards generality, so to speak, not away from it.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/41618 Ask a Question Download Related Notes/Documents
