Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Standard accounts of Turing Machines in the literature assume an infinitely long tape in at least one direction (and indeed infinitely time long to perform its computations). Clearly in practice no computer could have an infinite amount of cell storage either from the commencement of computations (even if we disregard the infinite amount of available time) or by adding blank cells at the end of the tape as required (which we'll eventually need if we assume infinite amount of time).

So my question is this: do the properties about Turing Machines obtained by assuming an infinitely long tape still hold of practical computing devices, for instance the existence of uncomputable functions? If so what does the assumption of an infinite tape buy us in terms making it easier to prove such properties?

share|cite|improve this question
Just a generalized comment: The infinite length of a Turing machine's tape is necessary when talking about complexity classes, which are infinite sets of computational problems (themselves, infinite sets). Intuitively, computational complexity is based on behavior at the extremes (as the input size grows to infinity, etc.). Of course, there are the "standard" type of concerns when comparing complexity notions to empirical/practical runtimes (e.g. there are a plethora of examples of exponential-time algorithms running faster in practice than polytime algorithms on "real-world" instances). – Daniel Apon Jan 11 '11 at 23:19
Note that for computability theorems, it does not matter wether we have one or many tapes and wether they are infinite in one or two directions. Runtime results are heavily affected by such a choice, though. – Raphael Jan 12 '11 at 10:53
Note also that you need only as much as one tape cell to achieve infinite runtime. – Raphael Jan 12 '11 at 10:55
Another note is that the "constructive" person favors the wording "arbitrarily extendable" or "potentially infinite" regarding the tape. – Tobias Raski Jan 12 '11 at 21:57
up vote 13 down vote accepted

Yes it makes a huge difference! A Turing machine with a finite tape is just a finite automaton, which we know are much less powerful. For example, a TM with a finite tape cannot compute a context free grammar. All of this is in theory, of course.

share|cite|improve this answer
And, as I pointed out in a different question, all models are wrong but some models are useful. While an actual computer can be accurately modelled as a finite state machine, how useful is it to think of a DFA with $2^{2^{40}}$ states? – mhum Jan 12 '11 at 2:32
Clearly it's not useful - that's why we think about Turing machines despite that all our computers have finite memory. But when we're in theoryland, a DFA with $2^{2^{40}}$ states is still a DFA. – Lev Reyzin Jan 12 '11 at 2:52
Exactly. The gap between the finite and the infinite is vast and important. – mhum Jan 12 '11 at 4:39
Our computers do not have infinite memory, but we assume that there is always enough for the computation at hand. That is, in practice, the same. – Raphael Jan 12 '11 at 10:50

Let me mention linear bounded automata (LBA) which can compute a proper subset of the function Turing machines can handle. LBA do model real computers better than Turing machines in the sense that no computation can use an infinite amount of space but there is no (constant) bound on space either. Of course, real computer do not have to have a linear bound.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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