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

CC BY-SA 2.5
2011-01-12T10:59:03.130Z
2011-01-12T10:59:03.130Z
Raphael
<p>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.</p>

CC BY-SA 2.5
2011-01-12T02:32:02.777Z
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
CC BY-SA 2.5
2011-01-12T02:52:38.377Z
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
CC BY-SA 2.5
2011-01-12T04:39:31.363Z
Exactly. The gap between the finite and the infinite is vast and important.
mhum
CC BY-SA 2.5
2011-01-12T10:50:56.210Z
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
CC BY-SA 2.5
2011-01-11T23:19:45.127Z
2011-01-11T23:19:45.127Z
Lev Reyzin
<p>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).</p>

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

CC BY-SA 2.5
2011-01-11T23:19:17.563Z
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
CC BY-SA 2.5
2011-01-12T10:53:08.593Z
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
CC BY-SA 2.5
2011-01-12T10:55:52.133Z
Note also that you need only as much as one tape cell to achieve infinite runtime.
Raphael
CC BY-SA 2.5
2011-01-12T21:57:58.187Z
Another note is that the "constructive" person favors the wording "arbitrarily extendable" or "potentially infinite" regarding the tape.
Tobias Raski
<computability><turing-machines>
Does an infinitely long tape make any difference when proving theorems about Turing Machines?
axiomsofchoice
# Does an infinitely long tape make any difference when proving theorems about Turing Machines?

(Asked by: username_0 on 2011-01-11)

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?

**Tags:** computability, turing-machines

> **Comments:**
> **username_1**: 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).  
> **username_2**: 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.  
> **username_2**: Note also that you need only as much as one tape cell to achieve infinite runtime.  
> **username_3**: Another note is that the "constructive" person favors the wording "arbitrarily extendable" or "potentially infinite" regarding the tape.  

---

## 2 answers

### Answer by username_4 on 2011-01-11. Score: 14 | Accepted answer

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.

> **Comments:**
> **username_5**: 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?  
> **username_4**: 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.  
> **username_5**: Exactly. The gap between the finite and the infinite is vast and important.  
> **username_2**: 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.  

---

### Answer by username_2 on 2011-01-12. Score: 4

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.


---

