2
$\begingroup$

Can you show me how to simulate Turing Machine with writing only on non-input fields on read-only Turing machine ?

I tried to do it be using internal states, but it provides me to infinitely many states, what is not allowed.
Any ideas ?

Edit
I consider standard Turing machines - one leftly-infinite tape.
read-only Turing machine is for me Turing machine such that it can't write on tape.
non-input fields - I mean part of tape where input is given. For example,
abcd#####...., machine can't overwrite abcd but it can overwrite each #. However, readonly can only read this tape, so no changes.

Edit II
I am searching for solution in which we use functions and Myhill-Nerode theorem. Can anyone provide this kind of solution ?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Please edit your question to define what you mean by "non-input fields" and "read-only Turing machine". A Turing machine doesn't have fields; it has a tape (or several tapes). Do you mean a Turing machine with a read-only tape, where the input is written, and a read-write tape? What do you mean by a "read-only Turing machine"? $\endgroup$ – D.W.♦ Mar 18 '17 at 19:07
  • $\begingroup$ I edited and clarified. $\endgroup$ – user54001 Mar 18 '17 at 19:10
  • $\begingroup$ Please don't use "Stuff. EDIT: Stuff". We have revision history, so you don't need to mark what has changed (click 'edited..' under the question to see prior revisions and what has changed). Instead, edit your question to read well for someone who reads it for the first time, with statements in a logical order. $\endgroup$ – D.W.♦ Mar 18 '17 at 19:11
  • $\begingroup$ en.wikipedia.org/wiki/Read-only_Turing_machine $\endgroup$ – D.W.♦ Mar 18 '17 at 19:14
  • $\begingroup$ @D.W. I think that you didn't understand my question. I meant: " Show that a Turing Machine $M$ that cannot write on the input portion of its tape can be simulated by a Turing Machine $N$ that does not write to its tape at all (not even in the blank part of the tape);" $\endgroup$ – user54001 Mar 19 '17 at 20:56
1
$\begingroup$

By Single-tape Turing Machines with write-protected input recognize only Regular Languages, a Turing machine that writes only on non-input fields accepts a regular language.

Any regular language can be accepted by a read-only Turing machine: just form a DFA for the regular language, then use that as the finite-state control of the Turing machine and scan the input from left to right.

Chaining those two facts together gives a full proof of the statement.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy