22
$\begingroup$

As you know there are many anomolies for the single tape Turing machines when the time is $o(n^2)$: multi-tape TM simulation, simulation of larger tape alphabet with just $\{0,1,b\}$, time constructability, non-tightness of time hierarchy theorem, ...

Also results like $\mathsf{DTime}(o(n\lg n)=\mathsf{Reg}$, and very model specific $O(n^2)$ time lowerbounds for simple problems (that don't translate to even superlinear lowerbounds on two tape TMs).

For space complexity, we use a model where we have a separate read only input tape, which is more natural and robust.

A TM model with multiple tapes (or at least 2 working tapes) would be much more robust and will not lead to anomalies like those I listed above. I once asked a prominent complexity theorist who has proven simulation results in the early years of complexity theory if he knows any improvements on one of these old results and the reply was that he doesn't think that "questions about the one tape model are that important".

If we change the standard model for time complexity to a two tape TMs, reasonable results in complexity theory will not change and we avoid these anomalies caused by particular model. So my question is:

is there any reason why the time complexity is still defined in terms of single tape TMs? (other than historical reasons)

Improve this question
$\endgroup$
11
  • 7
    $\begingroup$ I've never seen time complexity defined by single tape TMs. $\:$ I've only seen the robust time complexity classes defined by single tape TMs. $\;\;$ $\endgroup$
    – user6973
    Commented Apr 4, 2012 at 22:23
  • $\begingroup$ @Ricky, I meant time complexity of a problem is defined in terms of the time complexity of single tape TMs that can solve it. $\endgroup$
    – Kaveh
    Commented Apr 5, 2012 at 1:38
  • $\begingroup$ and I mean that I've never seen that done. $\:$ I've always seen, at minimum, random access. $\;\;$ $\endgroup$
    – user6973
    Commented Apr 5, 2012 at 2:18
  • 7
    $\begingroup$ but is that really the usual definition? what i have seen in textbooks is: 1) define single tape Turing machine (because it's simpler); 2) show how to extend to other variants, in particular multi-tape and random access; 3) show that all of these can simulate each other with at most polynomial slow down; 4) promptly forget about the model for the most part, at least until we need more subtle things like oracle machines and logspace reductions; so, like @RickyDemer, I would challenge the claim that this really is the usual definition. $\endgroup$
    – Sasho Nikolov
    Commented Apr 5, 2012 at 5:15
  • 1
    $\begingroup$ I don't have a answer for this, but, I just want to point this work to you by Yamakami (springerlink.com/content/u844854721p83870). This papers discusses about what happens when you add advice to a small machine (i.e. linear-time one-tape TM). It proves several class separations, but it does so using these one-tape TMs. These separations wouldn't work if you had other kind of TM. I think this is a nice example where you can prove cool things with one-tape and probably cannot with a different model. The moral is "one-tape matters when you deal with subtle things". $\endgroup$
    – Marcos Villagra
    Commented Apr 7, 2012 at 2:32

3 Answers 3

Reset to default
17
$\begingroup$

The other answers look very nice. I'd like to share a comment Russell Impagliazzo made years ago in a lecture, which has stuck with me ever since.

I think Turing may have preferred a single tape TM due to physical plausibility.

I pointed Russell to this thread days ago but, seeing as he's not here, I'd like his comment known, and will do my best to interpret it.

For a single tape TM, supposing a tape of infinite length (please stick with me), you can build a TM which just needs a bounded amount of energy per iteration. Imagine the tape as a long rod, and the head, which contains all TM logic, simply moves along this rod. (I think of it as a cute little geared contraption, using very primitive technology. The rod can have notches to help it along, and tape cell contents can just be a block slid orthogonally to the rod axis.)

On the other hand, how do you do this for a $k$-tape TM? If you have $k$ of the above contraptions, they must communicate their read status to the potentially extremely distant other heads, which takes unbounded amounts of energy (say you use wires, which necessarily leak heat), and moreover is not instantaneous, thus complicating the mechanism. If instead you kept the heads together and moved the tapes underneath them, you'd be using enough energy to move infinite-length tapes.. I don't see how to get bounded energy in either case. Tricks like shrinking tape increments (to get finite length) suppose an infinitely divisible universe, and violate things like Planck's constant and the holographic principle. Even ignoring these, the mechanisms in the head must be arbitrarily precise, which again causes energy problems, and is prodigiously complicated.

Of course, the first scheme has problems: the construction of the infinite tape with infinitely many notches, infinitely many suns to power solar collectors on the moving head, an infinite supply of cleaning and maintenance supplies, etc. Maybe some major breakthrough in quantum mechanics can let the $k$-tape heads communicate well, but now look how complicated our contraption is. In any case, I think Russell's comment is very, very interesting.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ i thought that Turing was trying to abstract the concept of "computing" and not abstracting a model for a physical device. in that case, a single-tape Turing machine captures cleanly the philosophical intuition that computation involves local access to large (infinite) memory $\endgroup$
    – Sasho Nikolov
    Commented Apr 8, 2012 at 1:29
  • $\begingroup$ I was expecting theoretical reasons (not realizibility of the models) but I find this answer very interesting, so I am accepting it. Thanks again. $\endgroup$
    – Kaveh
    Commented Apr 10, 2012 at 21:20
  • $\begingroup$ Keeping the tape heads in place it seems like we can make total energy loglinear or hopefully no worse than quasilinear in time by engineering a form of the Hennie-Stearns construction. I'm imagining the tapes rolled into increasingly larger loops as they extend in either direction... Or more imaginatively, on spools of tapes, 100 tapes to a spool, 100 spools to a rack, 100 racks to a warehouse, and on and on. Of course for bounded energy per iteration we'd need total energy linear in time. But quasilinear is better than the naive quadratic so I thought I would mention it. $\endgroup$
    – Dan Brumleve
    Commented Nov 22, 2017 at 20:59
16
$\begingroup$

I've seen texts define TIME( $f(n)$ ) using multi-tape Turing machines, but Sipser uses a single tape machine. You've almost surely first encountered this material through Sipser because it's so fabulously well written.

There is a crystal clear pedagogical reason why Sipser does this, namely the course just naturally flows that way because :

  • You should introduce the single tape machine before the multi-tape machine, otherwise steepens the learning curve.

  • There is no compelling reason to introduce the multi-tape machine before introducing O($\cdot$) and TIME($\cdot$) for single tape machines.

  • You should ideally compare the multi-tape machine with the single tape machine the moment you introduce the multi-tape machine, otherwise the prolonged ignorance will lead to additional confusion.

  • You could omit introducing the analogous TIME classes for multi-tape machines, thus simplifying notation overall.

There is no reason to quibble over conceptual cleanliness when the pedagogy so clearly dictates the easiest path, and every computer science undergrad must take this elementary course, including all those who still don't understand proofs.

Improve this answer
$\endgroup$
5
  • $\begingroup$ No, IIRC, my first encounter with TMs was Hopcroft and Ullman's first edition. But the reason I am asking this question is actually related to Sipser's nice textbook, I taught complexity theory based on Sipser and I felt that it would simpler and cleaner (with no essential material lost) for me and students if it was based on a multi-tape TMs. All these small technical details about restricted access of single tape TMs would be avoided and I could cover more interesting material in the limited time I had. Sipser is relaxed about using Church-Turing thesis, $\endgroup$
    – Kaveh
    Commented Apr 5, 2012 at 1:50
  • $\begingroup$ so I thought being relaxed about this part could also be fine. In the time hierarchy theorem part, he mentions that the extra log factor is not required if we had multiple tapes and it would be quite tight. This caused me to ask to see if there is any non-historical reason for using single-tape TMs for time complexity. It is no worst than using a separate read-only tape for space complexity (and again that is mainly because a single tape TM doesn't capture the intuition about small space complexity classes nicely). $\endgroup$
    – Kaveh
    Commented Apr 5, 2012 at 1:55
  • 2
    $\begingroup$ I don't see how one would even make sense of sub-linear space bounds without a separate input tape. $\;$ $\endgroup$
    – user6973
    Commented Apr 5, 2012 at 2:22
  • $\begingroup$ Yes, I'd assume SPACE is done differently, partially because you'll be doing sublinear bounds, which you probably won't for TIME. I'd argue for subscripting TIME or doing whatever Sipser does for SPACE if you wish to do it this way, certainly I'd want to talk about TIME or TIME_1 or whatever before multi-tape machines. $\endgroup$
    – Jeff Burdges
    Commented Apr 5, 2012 at 8:45
  • 1
    $\begingroup$ Interestingly, Sipser says merely "Turing machine" when defining SPACE(f(n)) but later changes the definition when discussing sublinear functions f, assigning an exercise on the equivalence for superliner f. I've taught this material from Sipser before. I hadn't thought too much about it at the time, but I'm pleased about it now. $\endgroup$
    – Jeff Burdges
    Commented Apr 5, 2012 at 13:08
9
$\begingroup$

The original Turing machine was described using a single tape:

www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf

So as you state in your question, this is mainly for historical reasons. Furthermore, there is always the tendency to ask what is the simplest model that can do something...

Also, since this topic is usually being taught very formally, it is just technically easier to describe a single tape machine than a two tape maching.

See also:

http://www.cs.utah.edu/~draperg/cartoons/2005/turing.html

Improve this answer
$\endgroup$

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.