# Does an infinitely long tape make any difference when proving theorems about Turing Machines?

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?

• 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). Jan 11, 2011 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. Jan 12, 2011 at 10:53
• Note also that you need only as much as one tape cell to achieve infinite runtime. Jan 12, 2011 at 10:55
• Another note is that the "constructive" person favors the wording "arbitrarily extendable" or "potentially infinite" regarding the tape. Jan 12, 2011 at 21:57

• 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?
• 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. Jan 12, 2011 at 2:52