3
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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). $\endgroup$
    – Daniel Apon
    Commented Jan 11, 2011 at 23:19
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented Jan 12, 2011 at 10:53
  • $\begingroup$ Note also that you need only as much as one tape cell to achieve infinite runtime. $\endgroup$
    – Raphael
    Commented Jan 12, 2011 at 10:55
  • 1
    $\begingroup$ Another note is that the "constructive" person favors the wording "arbitrarily extendable" or "potentially infinite" regarding the tape. $\endgroup$
    – Tobias Raski
    Commented Jan 12, 2011 at 21:57

2 Answers 2

Reset to default
14
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ 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? $\endgroup$
    – mhum
    Commented Jan 12, 2011 at 2:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – Lev Reyzin ♦
    Commented Jan 12, 2011 at 2:52
  • $\begingroup$ Exactly. The gap between the finite and the infinite is vast and important. $\endgroup$
    – mhum
    Commented Jan 12, 2011 at 4:39
  • 6
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented Jan 12, 2011 at 10:50
4
$\begingroup$

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.

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.