3
$\begingroup$

A multitape Turing machine is defined to have input only appear on one tape, with the rest of the tapes blank.

Are there any formulations of a Turing machine that allow other tapes to be not blank? Why does the condition that the input only appears on one tape exist?

$\endgroup$
  • 3
    $\begingroup$ Because it doesn't matter. You could always start with an input tape and blank working tapes and then write whatever you wanted on the working tapes before starting the actual computations. $\endgroup$ – Rick Decker Nov 21 '14 at 21:44
  • 1
    $\begingroup$ Well, randomised TMs have an extra tape filled with random bits. (@RickDecker) $\endgroup$ – Raphael Nov 21 '14 at 22:06
3
$\begingroup$

The restriction to a single non-blank tape at the start (and a single output tape too) is just convention – it makes the definitions a little simpler and maybe simplifies the analysis a little.

The reason we can make this restriction is that it makes no difference to the class of functions that are computable and it also makes no significant difference to the running time of algorithms. Any interesting Turing machine algorithm is going to need linear time since, otherwise, it can't even read all its input. For example, how would a Turing machine know to halt after $\log n$ steps? It's not read all its input in that time, so it doesn't even know what $n$ is!

This means that any linear-time preprocessing you do before the main part of your algorithm can't affect the asymptotic running time. So, in particular, you can check that, for example, your single input tape consists of three binary numbers separated by semi-colons, and copy those three numbers onto three separate tapes. Then you can run your main algorithm that thinks it has three different input tapes. Likewise, any Turing machine must run in time at least linear in the size of its output. This means that, if you have a machine whose output is spread across multiple tapes, you can postprocess that by copying it onto a single tape with the different parts separated by some special character.

As Raphael points out in his comment, there is at least one model that has more than one non-empty tape at the start. Probabilitstic Turing machines can be defined either by having multiple possible transitions from each state, each with an associated probability. Alternatively, they can be defined as deterministic Turing machine that has access to an infinite tape initialized with random bits. Note that this takes us outside the standard Turing machien model because we now have an infinite input. (This equivalence of a probabilistic machine on deterministic data versus a deterministic machine on random data is closely related to Yao's principle.)

$\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.