Re: A Definition of an Algorithm

The problem of giving a rigourous definition of algorithm that in some
sense agrees with the use of the word algorithm is informal English is
very difficult, and there has been little progress on it. I
emphasize that it is not a mathematical question but a philosophical
one to decide if a certain definition agrees with the informal use.

Several approaches to defining the word algorithm are in disfavor.
These approaches are formally consistant, but they do not correctly
capture the informal meaning of the word algorithm.

First, requiring the algorithm to be written in a specific language or
computing formalism (LISP, Turing machines, etc). Informally, we know
that the same algorithm can be implemented in different languages, so
it isn't satisfactory for a general definition of algorithm to consider
only one language or formalization.

Another approach that is not favored is to define two programs to have
the same algorithm if they compute the same function. There are often
many different algorithms (in the informal sense of the word) that
compute the same function. For example, there are at least a dozen
ways of sorting a list of numbers, all of which will compute the same
function. But nobody usually says, for example, that insertion sort
and quicksort are the same algorithm.

I don't have a reference handy, but I wager that any good introduction
to computability theory for computer scientists (the type of book that
includes discussion of regular and context-free languages as well as
Turing machines) will have at least a short discussion of the
difficulty of giving a formal definition of the word algorithm that
agrees with informal use. They will go on to discuss the Church-Turing
thesis, cite this as authority that the formalization they use at least
includes all possible algorithms, and then formally develop things
using that one formalism. I bet Knuth has good comments in the Art of
Computer Programming as well.

.

Relevant Pages

  • Re: pseudo code v/s algorithm
    ... the lack of formalism and precision. ... Pseudo-code is necessarily more ... ambiguous than any formally specified programming language. ... formal algorithm from it, and the risks that your pseudocode is ...
    (comp.programming)
  • P Versus NP
    ... determine whether every language accepted by some nondeterministic ... algorithm in polynomial time is also accepted by some ... L = Lfor some Turing machine M which runs in polynomial time} The ... We say that R is polynomial-time iff L R ...
    (sci.math)
  • Re: Mr. P and Ms. S
    ... determine whether every language accepted by some nondeterministic ... algorithm in polynomial time is also accepted by some ... L = Lfor some Turing machine M which runs in polynomial time} The ... We say that R is polynomial-time iff L R ...
    (sci.math)
  • P6 = NP (WAS: an oracle paradox)
    ... theory is the Turing machine,introduced by Alan Turing in 1936 ... solvable by some algorithm within anumber of steps bounded by some xed ... over .Then a language over is a subset L of. ... We say that R is polynomial-time i LR ...
    (sci.math)
  • Re: pseudo code v/s algorithm
    ... insert your language here) than code. ... There is absolutely no difference between algorithm and code, ... If I have an implementation or pseudo-code it cannot be ... Turing Machine or lambda-calculus in it, modulo the infinite memory ...
    (comp.programming)