Re: A Definition of an Algorithm


matthias@xxxxxxxxxxx wrote:
Noson Yanofsky writes:
The set of all programs is partitioned into equivalence classes.
Two programs are equivalent if
they are ``essentially'' the same program.

At least one problem with your analysis is that you first require that
the algorithms be written explicitly as primitive recursive functions
before you can decide whether the algorithms are the same. This
doesn't match the usually meaning of algorithm, in which it is possible
for one algorithm (insertion sort, say) to be written in many different
programming langauges: LISP, C, Java, etc.

That's why the Turing Machine standard is used.

These implementations of
the same algorhtm would be different: some might have explicit loops,
some might have no loops at all, using only recursive function calls,
but they would still be the same algorithm in the mind of the
programmer. After all, the programmer would probably say that she
``just wrote code for insertion sort in the new language.''

So a robust definition of algorithm must be neutral to the choice of
implementation language. This is a significant obstacle, which is why
the authors you cite in your paper don't attempt to do it.

To see what you are up against, look at the page
http://www.roesler-ac.de/wolfram/hello.htm . All the programs there are
the same algorithm: display ``Hello World'' on the output. This shows
how different programs implementing the same algorithm can be.

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

This is usually described by saying P1 and P2 compute the same
function. This extensional version of equality is usually viewed as
too coarse to define algorithms. For example, insertion sort and
quicksort are different algorithms, but they both sort.

You can do more devious things. Are the following the same algorithm?
They take a natural number as input and return a natural number as
output.

1) On input x, return x.
2) On input x, factor x into a primes. Then return x.
3) On input x, see whether there is a counterexample to Fermat's Last
Theorem a^n + b^n = c^n with a,b,c, and n >2 all less than x by testing
all possibilities. If you find a counterexample, go into an infinite
loop. If not, return x. (Note that because there is no counterexample
to Fermat's Last Theorem, this will always return x.)
4) On input x, send a post to sci.math containing x, then return x.

Most computer scientists would say that those descriptions are
``different algorithms'' but that they compute the same function.

So are 1) - 4) "essentially" the same program? You didn't answer my
question about what that key word means.

--- Christopher Heckman

.

Relevant Pages

  • Re: Delete all items in the list
    ... It is useless for predicting how fast that algorithm will run, ... For what it's worth, for very small lists, the while...remove algorithm is ... insertion sort for small lists, only kicking off a high-overhead but O ...
    (comp.lang.python)
  • Re: Best method to sort a linked list (in my case)?
    ... >> Each node´s x and y coordinates in the linked list changes for every frame. ... wich sort algorithm do you recommend? ... i thought that insertion sort would work as a linked list is insertion ...
    (comp.lang.c)
  • Re: How to demonstrate bigO cost of algorithms?
    ... > execution time) is PROPORTIONAL to n. ... insertion sort might be the fastest algorithm you have. ... Especially if reordering elements is expensive. ...
    (comp.lang.python)
  • Re: A Definition of an Algorithm
    ... the algorithms be written explicitly as primitive recursive functions ... doesn't match the usually meaning of algorithm, ... for one algorithm (insertion sort, say) to be written in many different ... the programmer would probably say that she ...
    (sci.math)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... This is a variation of my earlier counterexample: ... My counterexample graphs have D=2. ... > I have no counterexample to the lazy version of the algorithm, ... You've shown 2*ID iterations are not always sufficient. ...
    (sci.crypt)