"Elegant" may also mean practical so when Knuth talks about "some loosely defined aesthetic sense," he means intellectually artistic but he also means practical.
An interesting irony about this kind of overly restrictive mathematical definition of the word algorithm is that it represents an inelegant return to the actual basis of mathematics which is necessarily derived from finite examples. It is intellectually inelegant because it is so obviously insipid. The effort to make the impossible (an algorithm that can work ad infinitum) practical (no man made algorithm will ever work ad infinitum) comes at a cost of formalizing the pretense of making the fantasy look real by expressing it -as if- such things could be formalized even if they referred to infinite cases. As long as they do refer to infinite cases we want some algorithms to work ad infinitum. It is impossible to define complete universality other than using a word or two (as I just did.) So sub-program that can adapt in response to ongoing Input and Output and will run until it is exited is as much of an algorithm as a mathematical algorithm that can be applied to any value of an integer. Jim Bromer On Sun, Dec 2, 2012 at 8:18 AM, Jim Bromer <[email protected]> wrote: > From the definition of "algorithm" in Wikipedia > > In computer systems, an algorithm is basically an instance of logic > written in software by software developers to be effective for the intended > "target" computer(s), in order for the target machines to produce output > from given input (perhaps null). > > "Elegant" (compact) programs, "good" (fast) programs : The notion of > "simplicity and elegance" appears informally in Knuth and precisely in > Chaitin: > > Knuth: ". . .we want good algorithms in some loosely defined aesthetic > sense. One criterion . . . is the length of time taken to perform the > algorithm . . .. Other criteria are adaptability of the algorithm to > computers, its simplicity and elegance, etc"[22]Chaitin: " . . . a program > is 'elegant,' by which I mean that it's the smallest possible program for > producing the output that it does"[23] > > Chaitin prefaces his definition with: "I'll show you can't prove that a > program is 'elegant'"—such a proof would solve the Halting problem (ibid). > ------------------------------------------------ > > In other words, if you argue that an algorithm must terminate in a finite > amount of time, then it would imply that the Halting problem was not a > problem. We must have non-terminating algorithms even in mathematics > because most "elegant" mathematical systems are based on infinite counting > numbers and a abstract definition (or meta-definition) of such a system is > based on the application of the abstraction to produce a non-terminating > sequence of numbers. > > Elegance is an artisitic term, not a basis for a formal definition. > > The attempt to define an algorithm as a method that -must for all cases- > terminate in a convenient amount of time is naive. > > Jim Bromer > ------------------------------------------- AGI Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/21088071-c97d2393 Modify Your Subscription: https://www.listbox.com/member/?member_id=21088071&id_secret=21088071-2484a968 Powered by Listbox: http://www.listbox.com
