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?

  • 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$ Commented Nov 21, 2014 at 21:44
  • 1
    $\begingroup$ Well, randomised TMs have an extra tape filled with random bits. (@RickDecker) $\endgroup$
    – Raphael
    Commented Nov 21, 2014 at 22:06

1 Answer 1


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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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