<p>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.</p>

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

<ul>
<li><p>You should introduce the single tape machine before the multi-tape machine, otherwise steepens the learning curve.</p></li>
<li><p>There is no compelling reason to introduce the multi-tape machine before introducing O($\cdot$) and TIME($\cdot$) for single tape machines.</p></li>
<li><p>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.</p></li>
<li><p>You could omit introducing the analogous TIME classes for multi-tape machines, thus simplifying notation overall.</p></li>
</ul>

<p>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. </p>

CC BY-SA 3.0
2012-04-05T01:50:33.760Z
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,
Kaveh
CC BY-SA 3.0
2012-04-05T01:55:52.973Z
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).
Kaveh
CC BY-SA 3.0
2012-04-05T08:45:32.353Z
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.
Jeff Burdges
CC BY-SA 3.0
2012-04-05T13:08:18.917Z
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.
Jeff Burdges
CC BY-SA 3.0
2012-04-05T00:31:55.673Z
2012-04-05T00:31:55.673Z
Jeff Burdges
<p>The original Turing machine was described using a single tape:</p>

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

<p>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...</p>

<p>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.</p>

<p>See also:</p>

<p><a href="http://www.cs.utah.edu/~draperg/cartoons/2005/turing.html">http://www.cs.utah.edu/~draperg/cartoons/2005/turing.html</a></p>

CC BY-SA 3.0
2012-04-05T00:15:27.323Z
2012-04-05T00:15:27.323Z
Sariel Har-Peled
<p>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.</p>

<blockquote>
  <p>I think Turing may have preferred a single tape TM due to physical plausibility.</p>
</blockquote>

<p>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.</p>

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

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-04-08T01:29:35.587Z
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
Sasho Nikolov
CC BY-SA 3.0
2012-04-10T21:20:09.913Z
I was expecting theoretical reasons (not realizibility of the models) but I find this answer very interesting, so I am accepting it. Thanks again.
Kaveh
CC BY-SA 3.0
2017-11-22T20:59:09.340Z
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.
Dan Brumleve
CC BY-SA 3.0
2012-04-07T22:49:06.397Z
2012-04-07T22:49:06.397Z
matus
<p>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, ...</p>

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

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

<p>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".</p>

<p>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:</p>

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

CC BY-SA 3.0
2012-04-05T01:38:44.367Z
@Ricky, I meant time complexity of a problem is defined in terms of the time complexity of single tape TMs that can solve it.
Kaveh
CC BY-SA 3.0
2012-04-05T03:01:21.457Z
@Ricky, maybe I should change it to why we define complexity classes this way (if we define the complexity of a problem using RAMs).
Kaveh
CC BY-SA 3.0
2012-04-05T05:15:49.763Z
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.
Sasho Nikolov
CC BY-SA 3.0
2012-04-05T06:11:42.297Z
@Sasho, we don't really forget the model, e.g. time hierarchy theorem. The root issue is that the simulation works well only for $t \in \Omega(n^2)$. We have to go through all the trouble that is caused by simulating using only one tape. In any case, my question is not about this assumption, if you disagree just ignore that part, it is just my motivation for the question. I just want to know if there is a reason why we still use single tape TM definitions. So far I have seen two reason: 1. historical, 2. simplicity. The second one is not very convincing for me, but it is still a reason,
Kaveh
CC BY-SA 3.0
2012-04-05T06:16:42.587Z
[cont.] are there any other reasons?
Kaveh
CC BY-SA 3.0
2012-04-07T02:32:11.010Z
I don't have a answer for this, but, I just want to point this work to you by Yamakami (http://www.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".
Marcos Villagra
CC BY-SA 3.0
2012-04-07T05:40:35.797Z
@Marcos, thanks for the link. Here is a simpler example: we have a $n^2$ lowerbound for SAT for single tape machines. They may seem cool at first but the problem is that when the model is not robust proving a theorem about it is not as interesting, it is more about the model than about the problem.
Kaveh
CC BY-SA 3.0
2012-04-08T01:33:07.423Z
@Kaveh you don't even need SAT for this, right? Palindrome has a quadratic lowerbound on a single tape machine, as far as i remember
Sasho Nikolov
CC BY-SA 3.0
2012-04-08T05:32:42.537Z
@Sasho, that is correct, and IIRC, all these results can be obtained through the same communication complexity argument.
Kaveh
<cc.complexity-theory><turing-machines>
Why do we use single tape Turing machines for time complexity?
Kaveh
# Why do we use single tape Turing machines for time complexity?

(Asked by: username_0 on 2012-04-04)

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)

**Tags:** cc.complexity-theory, turing-machines
> **Comments:**
> **username_0**: @Ricky, I meant time complexity of a problem is defined in terms of the time complexity of single tape TMs that can solve it.  
> **username_0**: @Ricky, maybe I should change it to why we define complexity classes this way (if we define the complexity of a problem using RAMs).  
> **username_1**: 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.  
> **username_0**: @Sasho, we don't really forget the model, e.g. time hierarchy theorem. The root issue is that the simulation works well only for $t \in \Omega(n^2)$. We have to go through all the trouble that is caused by simulating using only one tape. In any case, my question is not about this assumption, if you disagree just ignore that part, it is just my motivation for the question. I just want to know if there is a reason why we still use single tape TM definitions. So far I have seen two reason: 1. historical, 2. simplicity. The second one is not very convincing for me, but it is still a reason,  
> **username_0**: [cont.] are there any other reasons?  
> **username_2**: I don't have a answer for this, but, I just want to point this work to you by Yamakami (http://www.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".  
> **username_0**: @Marcos, thanks for the link. Here is a simpler example: we have a $n^2$ lowerbound for SAT for single tape machines. They may seem cool at first but the problem is that when the model is not robust proving a theorem about it is not as interesting, it is more about the model than about the problem.  
> **username_1**: @Kaveh you don't even need SAT for this, right? Palindrome has a quadratic lowerbound on a single tape machine, as far as i remember  
> **username_0**: @Sasho, that is correct, and IIRC, all these results can be obtained through the same communication complexity argument.  

---

## 3 answers

### Answer by username_5 on 2012-04-07. Score: 17 | Accepted answer

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.

> **Comments:**
> **username_1**: 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  
> **username_0**: I was expecting theoretical reasons (not realizibility of the models) but I find this answer very interesting, so I am accepting it. Thanks again.  
> **username_6**: 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.  

---

### Answer by username_3 on 2012-04-05. Score: 16

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.

> **Comments:**
> **username_0**: 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,  
> **username_0**: 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).  
> **username_3**: 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.  
> **username_3**: 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.  

---

### Answer by username_4 on 2012-04-05. Score: 9

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>


---

