Turing machines are usually described as having an infinite tape (i.e. a tape with infinitely many memory locations), but I think it only needs to have a tape that has a sufficient but finite number of memory locations for the problem it's working on, (although, of course, it is unknown in advance how many locations will be needed.) Am I right?

Alternative question: if and when a Turing machine halts, has it only used a finite portion of its tape?

  • $\begingroup$ For normal TM, the work tape is the same as the input tape. Because the input may be of any length, the tape should be infinitely long. $\endgroup$ – xskxzr Apr 29 '18 at 4:06
  • $\begingroup$ Thanks for the comments. I should have proposed the following "theorem": if a Turing machine with the usual "infinite tape" halts on a particular problem, then there exists a Turing machine with a finite tape that will halt with the same problem. I gather from the discussion you will all agree with this. $\endgroup$ – Allan Apr 30 '18 at 11:17
  • $\begingroup$ This is not correct. I guess you have misunderstood some basic concept. Please formally define "halts on a particular problem", especially what is a "problem". $\endgroup$ – xskxzr Apr 30 '18 at 11:21

The answer to your alternative question is "yes". A Turing machine that halts, halts in a finite number of steps, and it can only move the head a finite distance from the starting position in a finite number of steps.

However, a Turing machine need not halt and may use up an ever growing number of tape positions as it executes. Further, we cannot in general tell how much tape a Turing machine will need to execute correctly.

Sometimes people speak of needing an "unbounded" or "ever extendable" tape rather than an "infinite" tape. About the only significance to this difference in wording is that the former wording makes it a bit clearer that the notion of a Turing machine should not be problematic to a finitist (though perhaps still for an ultrafinitist).

  • $\begingroup$ Even for a decider, the tape should be infinite because the memory needed may grow infinitely as the input varies. $\endgroup$ – xskxzr Apr 29 '18 at 4:02
  • $\begingroup$ For the sake of this question, I was taking "all" of the input as fixed, i.e. Turing machines that run on an initially empty tape, since that is how I took the intent of the question. You are completely correct that we usually want to consider Turing machines modeling functions and we want to consider the behavior for all inputs. $\endgroup$ – Derek Elkins left SE Apr 29 '18 at 4:07

The answer to your first question is "no": a finite amount of tape may not be enough. At the same time, the answer to your alternative question is "yes": once it finishes, a Turing machine has never used more than a finite amount of tape.

The fundamental issue is that in general, it's impossible to tell in advance how much, or whether it will finish in the first place.

Do Turing machines contain an infinite tape? I would say the answer to that question is "no".

Reason one: a Turing machine doesn't contain any tape, it uses tape. You can see this in its mathematical definition, which doesn't contain any tape or tape contents. The definition doesn't imply anything about how or when the tape it uses is supplied. It makes no difference to the Turing machine.

Reason two: a Turing machine never uses more than a finite amount of tape, in the sense that at any point during its computation, it can never have used more tape cells than it has made computational steps. However, at the same time, a Turing machine may use an infinite amount of tape, in the sense that there may be no bound on the amount of tape it will eventually use. Therefore, if you should start with a given, finite amount of tape for it to use, no matter how much you supply, it may not be enough: you may need to extend it on the fly, and you may need to do that infinitely often.

Therefore, only if we think of the tape as pre-supplied with the Turing machine (which we don't need to do), the only choice we have is to supply an infinite tape (which is clearly impossible).

When Turing invented his Turing machine, a computer was a woman making calculations on pieces of scrap paper. The nature of computation is such that there is no fixed limit on the amount of scrap paper (or tape) a computation may require. Nobody would ever say that a human computer is a woman (or man) containing an infinite amount of scrap paper, and therefore cannot really exist. Then why do I keep reading that Turing machines contain an infinite tape, and therefore cannot exist? It is wrong, or at least misleading: I've seen misunderstandings arise as a result. Therefore, I would prefer if courses on Turing machines would stop saying it.

  • $\begingroup$ On the one hand, the usage 'infinite' is useful, if we interpret it as "I don't want to (or can't) calculate how big my tape has to be to do X, but don't worry, I can make it as long as I please". Or more succinct, the meaning of 'infinite' here is really "big enough". In a sense, a Turing machine doesn't exist, even when equipped with finite tape, as it is a mathematical model for computation carried out by (wo)man or machine. For this model, 'infinite tape' is useful. $\endgroup$ – Discrete lizard Apr 29 '18 at 13:40
  • $\begingroup$ So, from an educational perspective, I think the 'infinite tape' is perfectly fine. Of course, it would be even better to add that we often call some physical creature, machine or software a 'Turing machine' if it 'adheres to the model' and then specifically use the 'big enough' specification of 'infinite tape'. Personally, I'd rather have teachers omit the fact that a Turing machine 'can exist' in the previous sense than that they omit the fact that a Turing machine is an abstract model. $\endgroup$ – Discrete lizard Apr 29 '18 at 13:46

Couldn't we say "a tape of indeterminately many cells," or "an indeterminately long finite tape"? I know it's wordier, but it might be clearer?

  • $\begingroup$ Is this a full answer or question? Could you elaorate? $\endgroup$ – Evil Sep 17 '19 at 21:05
  • $\begingroup$ I can't see why this should be more clear. To me this is a fancy way of saying "No one knows how long the tape is". $\endgroup$ – ttnick Sep 17 '19 at 21:19
  • $\begingroup$ Yes, I meant it as a full answer: Instead of saying that the tape is infinite, which is misleading, we could say, more clearly and precisely, that the tape is finite but indeterminately long. $\endgroup$ – José E. Burgos Sep 18 '19 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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