1
$\begingroup$

In my textbook, enumeration machines are defined as possessing a special write-only output tape, which they can write characters to, but not move the head of. When they hit the print state, the string on the output tape is enumerated and reset to a blank tape.

Is this equivalent to the model of enumeration machines where they have just one tape, the contents of which is enumerated (but not cleared) whenever they hit the print state? One direction seems easy, but I'm not sure how to prove you wouldn't need the extra tape.

$\endgroup$
3
$\begingroup$

Multitape machines are equivalent to single tape machines. You can simulate several tapes on a single tape. In particular, in order to simulate the "print state" model using the "write-only output tape" model, you simulate an extra output tape, and whenever the print state is reached, you copy the contents of the extra output tape to the write-only output tape. Therefore both models are equivalent.

More generally, all reasonable Turing machine models are equivalent. This is a special case of the Church–Turing hypothesis.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.