Re: Provability

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.
--
Robert Israel israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
.

Relevant Pages

  • Re: Provability
    ... terminates with a well-defined and asserted result. ... the definition of algorithm. ... the standards of rigor for a mathematical proof. ... because of the curry-howard isomorphism ...
    (sci.math)
  • Re: Provability
    ... terminates with a well-defined and asserted result. ... the definition of algorithm. ... computer science does consider a partial recursive function is to be "an ... situations exist is most of classical mathematics: ...
    (sci.math)
  • Re: Provability
    ... terminates with a well-defined and asserted result. ... the definition of algorithm. ... the standards of rigor for a mathematical proof. ... math is for the ages. ...
    (sci.math)
  • Re: Provability
    ... terminates with a well-defined and asserted result. ... the definition of algorithm. ... fact is that standard terminology in mathematics and theoretical ... situations exist is most of classical mathematics: ...
    (sci.math)
  • Re: Provability
    ... terminates with a well-defined and asserted result. ... the definition of algorithm. ... the standards of rigor for a mathematical proof. ... math is for the ages. ...
    (sci.math)
Quantcast