Re: Provability

In article
<rbisrael.20071025044151$5f90@xxxxxxxxxxxxxxxx>,
Robert Israel <israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx>
wrote:

Michael Press <rubrum@xxxxxxxxxxx> writes:

In article
<1193251799.743613.21490@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Marshall <marshall.spight@xxxxxxxxx> wrote:

On Oct 24, 10:57 am, Michael Press <rub...@xxxxxxxxxxx> wrote:

An algorithm is a procedure that takes input and
terminates with a well-defined and asserted result.
That it does terminate with the asserted result must be
proven. Until we accept the proof, it is not an
algorithm. The notion of right answer is not part of
the definition of algorithm.

That definition is extremely narrow, and does not correspond
to any usage of the term that I can recall in many years
of being a programmer.

I'm not even sure I'd buy in to the "well-defined" part.
Having a "probabilistic algorithm" doesn't sound like
a contradiction in terms. In fact, Googling it just
now it gets a lot of hits. Neither does "proven correct,
proven terminating algorithm" sound redundant.

I fail to see the utility in defining an algorithm
to be no more than a partial recursive function.
A theorem is not a theorem until it is proven.
What is your standard for implementing a method
into production code?

Whether you see the utility or not is beside the point. The
fact is that standard terminology in mathematics and theoretical
computer science does consider a partial recursive function is to be "an
algorithm", and there is a difference between "algorithm A solves problem P"
and "we have a proof that algorithm A solves problem P". Similar
situations exist is most of classical mathematics: objects may have
certain properties even if there is no proof that they have those
properties.

Few enough people think of an algorithm in the way I
do, A.A. Markov and Donald Knuth take an algorithm to
be more definite than a partial recursive function.
Knuth writes at length in ACP, 1.1. Here is a portion
quoted in Wikipedia.

1. Finiteness: "An algorithm must always terminate
after a finite number of steps ... a very finite
number, a reasonable number"

2. Definiteness: "Each step of an algorithm must be
precisely defined; the actions to be carried out must
be rigorously and unambiguously specified for each
case"

3. Input: "...quantities which are given to it
initially before the algorithm begins. These inputs are
taken from specified sets of objects"

4. Output: "...quantities which have a specified
relation to the inputs"

5. Effectiveness: "... all of the operations to be
performed in the algorithm must be sufficiently basic
that they can in principle be done exactly and in a
finite length of time by a man using paper and pencil"

Apparently, only I consider a proof to be part of an algorthm.

--
Michael Press
.

Relevant Pages

  • Re: random numbers function
    ... And therefore not guaranteed to terminate, ... to which I offer no perfect remedy. ... the algorithm terminates with probability 1 but Big-O is not ... I don't remember which regular posters castigate qsort for its ...
    (comp.programming)
  • Re: random numbers function
    ... And therefore not guaranteed to terminate, ... the algorithm terminates with probability 1 but Big-O is not ... realistic solution is to abandon the plain definition of Big O and ...
    (comp.programming)
  • Re: Deterministic Algorithm for Random Number Generation Using Coin Flips
    ... "niggers" that are much more intelligent than you are. ... algorithm and passed it off as his own. ... "guaranteed to terminate", ... I want an algorithm that given a binary flatly-distributed generator, ...
    (sci.math)
  • Re: How to prove that a random sort algorithm converges?
    ... There are more than one way to prove the algorithm. ... Is there a way to find the upper bound? ... there is no finite upper bound. ... algorithm in the simple case above wouldn't terminate after 64 steps. ...
    (sci.math)
  • Re: Deterministic Algorithm for Random Number Generation Using Coin Flips
    ... -the algorithm can guarantee that there is 0 probability that the ... algorithm will run forever. ... generator that is guaranteed to terminate after finite throws? ... the rng be random? ...
    (sci.math)
Loading