random

[David C. Ullrich]

On Sun, 3 Jun 2001 19:29:00 +0200, "Alex Martelli" <aleaxit at yahoo.com>
wrote:

>"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.

I was certainly aware that people sometimes use the word this
way and sometimes use the word that way. Which usage is more
common is not something that one can decide by finding one
web site.

And which usage is more common is really not important. Delete
what I said about halting being part of the definition of
"algorithm" if you want. The _point_ I was trying to make is
that there is a reason that people are sometimes more interested
in algorithms that are guaranteed to halt - it's not just an
arbitrary detail inserted for the fun of making the (utterly
nonstandard and highly controversial) definition longer.

>Once people stopped using "algorithm" to mean only what is
>today properly called "deterministic algorithm"

Hmm. So you think that formerly the word "algorithm" did
include the requirment that it halt. Answer me this:
In that quote from JVN, do you surmise that the "arithmetic
methods" he was referring to were algorithms that halt, or
do you think he meant to include RNG's that do not return
RN's?

Me, I'm running out to write a paper on the halting problem.
Now that the meaning of the word "algorithm" has changed
there _is_ an algorithm to determine whether a TM halts:
Run it and wait, forever if necessary.

Gonna be famous, unless the referee thinks it's silly
and rejects the paper.

> 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,

And arguably less relevant in support of the idea that an
"algorithm" is not required to halt. (But never mind that,
I don't care how we define words as long as we don't prove
falsehoods by letting the definition drift between hypothsis
and conclusion.)

>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. 

You'd better not require _one_ bit to be generated
in finite time.

>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?

We are not getting "perfectly random" bits if we use an arbitrary
timeout. (Defined elsewhere - the meaning of the phrase seemed clear
to everyone else.)

If we're going to settle for an RNG that's good enough for one
particular purpose it does not require any magic to get this;
doesn't take Omega to do. An RNG that's good enough for one
particular purpose is not what I've been talking about.

Even if we're only interested in one particular problem, we
are still in a state of sin using an arithmetic generator
that's good enough unless we _verify_ that it _is_ good enough
to answer the current question to the accuracy requested.

>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"?

Also I realized last night that I don't think that the bits of Omega
are any good whatever for an RNG, even if we _could_ know somehow
what the bits were. I want to look at the "definition" of Omega
again before expanding on this...

>Alex
>
>
>
>



David C. Ullrich
*********************
"Sometimes you can have access violations all the 
time and the program still works." (Michael Caracena, 
comp.lang.pascal.delphi.misc 5/1/01)