How would I go about proving that a TM that can both read and write at the same time is equivalent to a typical TM?

For constructing a read+write TM from normal TMs, my idea is to split the state of writing and reading simultaneously to two separate states (one for writing and one for reading). Not quite sure if this works..

Also, am not sure how to construct a normal TM from read+write TM.

Thank you!

  • $\begingroup$ I think your idea (or something similar) may work (at least, it seems intuitive), but I've not written many proofs in the context of computation theory. Maybe have a look at how other people have proven other equivalences between two TMs and follow a similar approach. $\endgroup$ – nbro Nov 14 '19 at 1:04
  • $\begingroup$ This is a good question but can you add some precision to the problem statement? How are you defining read and write simultaneously? Are there multiple heads? Can the write depend on the read or only the previous state? $\endgroup$ – Sam Jones Nov 15 '19 at 11:50

Your Answer

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

Browse other questions tagged or ask your own question.