1
$\begingroup$

Consider a Turing machine with input alphabet $\{a,b\}$ that computes the following function:

$$ f(w, v) = \begin{cases} w & \text{if } \operatorname{length}(w) > \operatorname{length}(v), \\ v & \text{otherwise}. \end{cases} $$

I wish to use a TM with two tapes, the first of which contains the input string, say encoded as $*w*v*$. I'm not sure, having read several books, which tape is the output tape in this case. For example, the output tape for a TM of two tapes is the input tape or the second tape? If I use three tapes, is it correct that one of them contains the input, another is a working tape, and the third is the output tape?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Unless otherwise specified, it is usually up to you to decide on which tapes the input and outputs will be placed (possibly on the same tape, e.g., in a machine with only one tape). One possible choice is to have a read-only input tape, some read/write working tapes, and one read(/write) output tape. $\endgroup$
    – Steven
    Nov 7, 2019 at 17:44
  • $\begingroup$ The output tape in the above comment should have been (read/)write, i.e., you need to be able to write to it. $\endgroup$
    – Steven
    Nov 7, 2019 at 19:28

1 Answer 1

Reset to default
3
$\begingroup$

There is no generally accepted definition of Turing machine. Various authors use various models. One author's definition might specify the output tape, another's might leave the choice to the Turing machine designer.

The reason that we don't care about this "calling convention" is that it doesn't matter from the point of view of computability (and, to a large extent, from the point of view of complexity). All of the different variants of Turing machine are Turing-equivalent; the languages they decide are the computable languages, and the languages they recognize are the recursively enumerable languages.

If you're writing a paper, the choice of which model to use is up to you. But this hardly ever comes up, since Turing machines are usually described very informally. The informal description can be implemented in any reasonable variant of the Turing machine model.

Improve this answer
$\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.