No, and ...

Posted Jun 5, 2009 15:10 UTC (Fri) by sepreece (guest, #19270)
In reply to: No, and ... by flewellyn
Parent article: Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)

"Who on Earth taught you that algorithms must be finite and deterministic?"

Well, curiously enough, that was Knuth (or, rather, another brilliant CS professor teaching from Knuth's book).

The Art of Programming, Volume 1: Fundamental Algorithms, pp4-6 (first edition). "... an algorithm has five important features: 1) Finiteness. An algorithm must always terminate after a finite number of steps. ... A procedure that has all the characteristics of an algorihm except that it possibly lacks finiteness may be called a 'computational method' ... 2) Definiteness. Each step of an algorithm must be precisely defined. ... 3) Input ... 4) Output ... 5) Effectiveness ..." [in each case the "..." represents a body of explanatory text).

You think Knuth should not be allowed to teach?

No, and ...

Posted Jun 5, 2009 16:56 UTC (Fri) by flewellyn (subscriber, #5047) [Link] (1 responses)

Knuth seems to be going by a restricted definition of "algorithm", then. From what I've read, "computational method" and "algorithm" fade into each other depending on whose definitions you use.

Perhaps I spoke hastily with the "should not be allowed to teach".

No, and ...

Posted Jun 6, 2009 2:03 UTC (Sat) by chad.netzer (subscriber, #4257) [Link]

Yes, you did. :) The fact is, the definition of "algorithm" in CS is not unlike the definition of "species" in biology; no one can quite agree on a rigorous definition.

http://en.wikipedia.org/wiki/Algorithm#Termination
http://en.wikipedia.org/wiki/Algorithm#By_complexity