No, and ...

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

>> I was taught that algorithms were finite, deterministic, and halted, which rules out a lot of programs.

You were taught very wrongly! There absolutely are non-deterministic, non-halting, infinite algorithms. In fact, those make up a large portion of computer science and AI research. Who on Earth taught you that algorithms must be finite and deterministic? That person should not be allowed to teach.

No, and ...

Posted Jun 5, 2009 15:10 UTC (Fri) by sepreece (guest, #19270) [Link] (2 responses)

"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