>
> Well, the existence of infinities in your inputs complicate things more
> than a system where everything is finite. A turing machine with a
> fixed-length tape is far less interesting to prove things about than
> otherwise.

This is generally true if you have actual infinities as inputs, but for 
the case when you merely have arbitrarily large (but always finite) 
inputs I'm actually having trouble thinking of a case where this is true 
that doesn't involve only "small" finite values (or in which you allow 
some unbounded quantities but not others, like in your comment on finite 
programs being O(1)).  Perhaps you had an example in mind?

I'm more used to seeing "arbitrarily large" or "arbitrarily small" 
values used to simplify things.

> Stuff like big-O notation only uses infinities because you're again
> assuming your functions have infinities in them. Every program on a
> finite machine finishes in O(1) time.
>

My example with big-O notation was actually slightly different than 
that.  If we really restrict ourselves to only bounded quantities, then 
it's impossible to actually define big-O notation since it's defined for 
"sufficiently large inputs".  Thus saying that every program on a finite 
machine finishes in O(1) times is sort of disallowing infinity in one 
area while letting it slip by in another.

My point with big-O notation was instead that the allowance of 
arbitrarily large inputs in the definition is actually massively 
simplifies the problem.  Without it we'd probably be restricted to an 
analysis where constant multiples in the running times really do matter, 
making it much harder to analyze the running times of programs in a 
general way.

Thus I think it's misleading to say that "big-O notation only uses 
infinities because you're again assuming your functions have infinities 
in them".  Rather big-O notation uses infinities because it greatly 
simplifies the analysis of programs (and it practice it turns out that 
the analysis for the case with arbitrarily large inputs carries over 
pretty well to the real-world case of large but bounded inputs).


I'm not entirely sure that we actually have different viewpoints on 
this, and it's possible that I'm just misunderstanding your argument. 
I'm mostly basing my assumptions about your position on your comment:

> Funny enough, infinities make things much more complicated. That's why
> virtually every bit of math deals with infinities.

Which seems to run counter to my experience, where I'm used to seeing 
unbounded values allowed as a simplifying assumption, and see them as 
common because it's such a powerful tool for allowing general statements 
about whatever branch of math you're considering.

Post a reply to this message