Re: A Definition of an Algorithm


noson@xxxxxxxxxxxxxxxxxxxxx wrote:
Dear All,

I think this group might be interested in a paper I just posted.
The title is

Towards a Definition of an Algorithm

An algorithm is a terminating procedure designed to solve a certain
problem. My guess is you want to make that more precise.

Abstract: We define an algorithm to be the set of programs that
implement or express that algorithm.

This is a circular definition, and you haven't defined "programs",
either.

The set of all programs is
partitioned into equivalence classes. Two programs are equivalent if
they are ``essentially'' the same program.

Maybe this should be: "Two programs P1 and P2 are equivalent if for all
inputs, P1 and P2 produce the same output" ?

Well, that's enough for tonight.

--- Christopher Heckman

.

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... equivalence classes, not 11117. ... Bill Cox algorithm that you verified up to 8 nodes, ... not in your implementation) is in my rendering of Bill Cox's ... It would help if you could give two graphs that are not ...
    (sci.crypt)
  • Re: A Definition of an Algorithm
    ... same algorithm", so now all we need is the way do define this relation. ... To define/or to describe the term "algorithm" by ... means of some notions which include term "algorithm" ?? ... then use the equivalence classes for your new notion. ...
    (sci.math.research)
  • Re: JSH: Whats happening now?
    ... >> You are so unlucky. ... My algorithm shows that 3 is not ... --- Christopher Heckman ... Prev by Date: ...
    (sci.math)
  • Re: diophantine equation 1/x + 1/y = 1/n
    ... If you want only positive solutions, ... plz tell me the algorithm to solve this problem. ... this fraction reduces to 1/x. ... --- Christopher Heckman ...
    (sci.math)
  • Re: Calculating the running time of an algorithm?
    ... Gabriel Cunningham wrote: ... For an example of an algorithm that that takes exponential time, ... --- Christopher Heckman ...
    (sci.math)