Comment by jerf | Hacker News Reader

Comment by jerf | Hacker News Reader

Parent Full thread

"We imagine Turing Machine memory having an infinite tape which is just there, not having a tape that must be generated as the head moves."

This is one of those times when you're probably better off saying and thinking "unbounded" rather than "infinite". The point of a TM is not that it "literally" (to the extent that term applies anyhow) has "infinite" cells in it, the point is that there is no point in the computation in which it will reach for another cell and be told that there isn't one. (So there isn't even a way to represent that.) Many "infinite" things are better conceived of as "unbounded". For another example, "infinite lists" in Haskell. Obviously, they can not concretely manifest infinitely many cells in memory, but there is no point at which the runtime will reach for "the next cell" and be told it has reached the end of the list.

That is also why it's better to model our real computers with TM math, even though they obviously do not have literally infinite amounts of memory. As long as a software process runs along and is never told that it is out of memory when it asks for more, we get fairly TM-like behavior, or we get a crash if it does run out. By contrast, while the FSM model is in some sense more mathematically accurate, it is less useful for modeling real computers, since it is so weak.

I think this formulation also better intuitively explains why we use infinity so often in our proofs; by saying "and there's always another one if you want it", we remove the case where we have to handle there not being another one. And that case can get quite hairy, as anyone who has watched their machine self-immolate after it discovers it is out of RAM can attest to. :) (It can also be every bit as mathematically tedious to deal with, too.)

The further I got through grad school, the more I said "unbounded" rather than "infinite".

I once read an analogy that said to think of the "infinite tape" of a Turing machine as similar to how physicists think about infinite parallel plates, etc. The infinite case can be easier to treat theoretically, and also give key insights, that might not be attained in the finite case. Even though you have an understanding that any real system is finite, imagining an infinite system is a useful approximation.

And as long as you're operating in a region that's not close to the edge, the edges don't make a difference to the outcome.

Likewise, while real machines are really DFA's since they have a finite amount of memory, thinking of them as having infinite memory is a much better approximation. And as long as you don't "get close to the edges" by e.g. trying to allocate more memory than your machine has available, it works perfectly.

"The further I got through grad school, the more I said "unbounded" rather than "infinite"."

I think there's a huge difference between simply saying "unbounded" compared to going through that detailed explanation you just gave. In the latter case, it's very clear what the difference is. But without the explanation I'd guess that people will think something like this:

    unbounded -> without bound -> infinite

In other words, without the explanation "unbounded" becomes a synonym for "infinite".

"Unbounded" means "any finite number, no matter how large." For many people, this might be what they think of when they hear "infinite," but in mathematics, "infinity" is an entirely different concept.

Even in math "infinity" often means "unbounded". For example, in real analysis if we have a sequence x_n, we write lim x_n = ∞ to mean "given any real number alpha, we can find a natural number K, such that x_n >= alpha for all n > K".

As I mention in another comment, I am specifically referring to the fact that when we computer scientists or discrete mathematicians use the term in proofs, we were more often interested in the "unbounded"ness than something with "actual" infinite cardinality... the fact that I understand the difference is precisely why I tended to start saying unbounded more often. Using infinity to mean unbounded is really too powerful, and a proof should use the least power necessary. (It was only an intuitive feeling at the time; I have a much better understanding of that fact now.)

When infinity is the relevant concept, use it.

This reminds me of the distinction between random and arbitrary. Seems to trip people up sometimes.

The relevant distinction isn't between "bounded" and "finite", but between the size of a container and the size of its elements.

The difference between "bounded" and "infinite" is the difference between "measure" and "cardinality". That is , "bounded" refers to a notion of distance, while "finite" refers to a measure of count. There are bounded infinities (such as the set of all rational or numbers between 0 and 1), but there are no unbounded finities.

A container that contains finite objects of all sizes must be an infinite/unbounded container.

Depending on the context unbounded and infinite may mean very different things, for example the surface of a sphere being unbounded but finite.

That's why I didn't simply drop the word infinite. There are cases where it is appropriate. What is the cardinality of the natural numbers? Infinite... "unbounded" is definitely not right there. But when we use infinity in proofs, we are more often using it to mean "unbounded" rather than truly a "manifested infinity", to use a sloppy phrase; we're using it to get rid of the nasty edge case, not because we expect a real implementation of whatever the proof is proving to actually require infinite RAM.

Also, by "we", I should clarify I mean discrete mathematicians and computer scientists, who are usually dealing in the discrete case. In the continuous case, infinities come up "for real" more often.

A sphere is bounded but infinite*

http://en.wikipedia.org/wiki/Compact_space

*Infnite cardinality of points, not infinite in measure.

Reply on news.ycombinator.com