Re: Provability

On Wed, 24 Oct 2007 20:58:57 -0700, Michael Press <rubrum@xxxxxxxxxxx>
wrote:

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.

Nobody has claimed that you see the utility in that
definition. That _is_ the definition.

Do you really think that if you don't see the utility
in a certain definition it follows that it cannot
in fact be the definition of whatever? Is that a
special property of you in particular, or is it
true that a definition is not a definition unless
_everyone_ sees the utility in it?

A theorem is not a theorem until it is proven.
What is your standard for implementing a method
into production code?


************************

David C. Ullrich
.

Relevant Pages

  • Re: Provability
    ... terminates with a well-defined and asserted result. ... the definition of algorithm. ... proven terminating algorithm" sound redundant. ... michael's happens to be one of the more useful definitions ...
    (sci.math)
  • Re: Provability
    ... MoeBlee wrote: ... terminates with a well-defined and asserted result. ... the definition of algorithm. ... proven terminating algorithm" sound redundant. ...
    (sci.math)
  • Re: Provability
    ... terminates with a well-defined and asserted result. ... the definition of algorithm. ... proven terminating algorithm" sound redundant. ... I fail to see the utility in defining an algorithm ...
    (sci.math)
  • 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)
Loading