|
![](/i/fill.gif) |
>
> 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
|
![](/i/fill.gif) |