random

[Alex Martelli]

"David C. Ullrich" <ullrich at math.okstate.edu> wrote in message
news:3b1a564f.2986926 at nntp.sprynet.com...
    ...
> > but some would say the finite
> >program is not "an algorithm" because it's not finite in time -- it
> >may never halt
>
> Halting _is_ part of the standard definition of "algorithm";
> this is not what "some" would say.

Sorry, you are simply wrong.  Take for example (seems to
be in Google's cache only, not at the originally referenced
URL, so be fast in checking it:-):

http://www.google.com/search?q=cache:2nixCLVhh-0:phobos.cs.unibuc.ro/mitecs/
work/dietrich_r.html+probabilistic+algorithm+terminate&hl=en

"""
First, mathematicians and computer scientists sometimes sharply
restrict the definition of "algorithm." They take the definition of
"algorithm" given here, and use it to define the notion of an effective
procedure. Then they define an algorithm as an effective procedure
which always halts or terminates.
"""

Note the "sometimes".  I concur with this author.  Many say
"algorithm" without requiring absolute certainty of termination,
while others use "effective procedure" for the general concept
and only allow the use of the word "algorithm" when certainty
of termination can also be proven.

Once people stopped using "algorithm" to mean only what is
today properly called "deterministic algorithm" and include
also what is today called "probabilistic algorithm", it was, I
think, quite proper that termination constraints fall also by
the wayside.  Consider just one example,
http://www.di.unipi.it/~augusto/pub/selection/papers-pdf/dc.pdf
the probabilistic algorithm it analyzes is by itself not necessarily
terminating.  "MOST OFTEN" it will terminate with a provably
correct result quite a bit sooner than its deterministic brother,
but quite possibly it might just keep going on and on instead.

Not quite the exact kind of probabilistic algorithm most used
today (e.g. for probabilistic testing of primeness) which does
terminate in finite time BUT maybe with a wrong answer --
arguably more useful when applicable, since I _known_ where
my algorithm hasn't terminated (yet) so that corrective action
may be taken.  Of course, _in practice_, as long as probability
of non-termination (just like, probability of the answer being
the wrong one for the more often used kind of probabilistic
algorithm) can be set as small as desired by appropriate steps,
the actual usefulness of the probabilistic approach is just as
good as that of the deterministic one.


> There's a _reason_ it's part of the definition. Elsewhere
> you've claimed to be an engineer, seeming to imply you're
> interested in practical matters. If you have a solution to
> a problem but the "solution" takes infintely much time
> does it really seem like a _useful_ solution in practical
> terms?

Sure, just like a solution that may not in fact be one (the
answer from the other kind of probabilistic algorithm).  On
the practical plane, probabilities, when high enough, are
amply sufficient -- in real life we ain't gonna get any
certainty anyhow.


> Like say we want to use Omega to give a "perfect"
> arithmetic RNG. We can do that. Except that when
> we call x = rand() the call _never_ _returns_.
> If you're really interested in RNG's that never
> return then I take back everything I've said,
> yes, JVN was wrong, there's no problem with
> arithmetic RNGeneration.

I only need a high-enough probability of termination
within a given finite time for one requested random
bit.  Say I monitor the process from the outside and
if it's not done in (whatever) I raise an exception,
take some corrective action, kill the runaway process.

I don't request an infinite number of bits to be
generated in finite time, OBVIOUSLY.  I don't need
infinitely many bits for whatever use I'm putting
that random-number to -- just one bit at a time.


> >So where's the "state of sin" in this arithmetical and
almost-algorithmical-
> >except-for-the-little-detail-of-finiteness approach to randomness?
>
> The quote from JVN was about someone _using_ arithmetic methods to
> generate random numbers. If someone is "using" an RNG that _never_
> _returns_ then he is _not_ generating random numbers. (A fortiori
> he is not using arithmetic methods to generate random numbers.)

On those occasions when the algorithm (or effective procedure,
or call it as you wish as long, as you don't call it late for dinner)
is not terminating [within some needed time], detection of the
fact and a back-up plan will be needed.  So what?  Aren't random
bits still emerging -- one after the other -- in finite time on most
occasions, with whatever probability we request if we can devote
sufficient resources to the task?

I strongly doubt this method is practical or can be made practical,
differently from many other uses for probabilistic algorithms, though
I would hardly be astonished if somebody more clever or lucky than
me did manage to come up with a practical use.  But, so what?  Where
was "practically useful" requested to avoid "a state of sin"?


Alex