Consider Turing machines (with the Busy Beaver "design specifications")
that must write a 1 whenever they read a 1 (i.e., "write once").

${}$1. $\:$ Is the halting problem decidable for these machines?

If those specifications are modified to use a [one-way infinite] tape instead,

${}$2. $\;$ Is the halting problem decidable for the resulting type of machines if they

a. $\;$ stay where they are
b. $\;$ halt

whenever they try to move off the end of the tape?

  • $\begingroup$ I fail to see any reason why the usual proof of non-computability of the busy beaver function would not apply to your cases, but I may be missing something. Can you elaborate? $\endgroup$ – Tsuyoshi Ito Jan 28 '12 at 21:40
  • $\begingroup$ I fail to see why my cases would be Turing-complete. $\:$ (Although I now notice that this is equivalent to the halting problem for those types of machines.) $\;\;$ $\endgroup$ – user6973 Jan 28 '12 at 22:20
  • 1
    $\begingroup$ If your definition of write once is the usual one then Sipser 2006, Problem 3.10 should answer your question. Having a one-sided tape doesn't change anything (in fact that is the version used by Sipser in his book). $\endgroup$ – Kaveh Jan 28 '12 at 22:20
  • $\begingroup$ err... yeah, that would do it. $\;$ If you post that as an answer I'll accept it instead of user3158's. $\;\;$ $\endgroup$ – user6973 Jan 28 '12 at 22:34
  • 1
    $\begingroup$ @Ricky, the answer was posted before I commented, so I think you should accept user3158's answer. ps: strictly speaking, question oat the level of textbook exercises are off-topic for cstheory (but to be fair, I probably would not recognize this if I hadn't checked the exercises in Sipser last week). $\endgroup$ – Kaveh Jan 28 '12 at 22:55

Ad 1. Write-once TMs are equivalent to ordinary TMs (I think this is an exercise in Sipser, but I don't have the text at hand to confirm) so $\rm woBB$ is uncomputable.

Ad 2. No. The usual zipper encoding also works for write-once TMs, so write-once TMs that never move past the end of the one-way infinite tape are equivalent those with two-way infinite tape. Therefore $\rm owwoBB$ is uncomputable, and the choice of behaviour when moving past the end of the tape doesn't affect this.

  • $\begingroup$ Note to other people reading this answer: This answered my question as it was when this answer was posted; I'm giving Kaveh a chance because he gave the reference. $\;$ $\endgroup$ – user6973 Jan 28 '12 at 22:48

Your Answer

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