"Fredrik Lundh" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > Christian Stapfer wrote: > >> As to the value of complexity theory for creativity >> in programming (even though you seem to believe that >> a theoretical bent of mind can only serve to stifle >> creativity), the story of the discovery of an efficient >> string searching algorithm by D.E.Knuth provides an >> interesting case in point. Knuth based himself on >> seemingly quite "uncreatively theoretical work" (from >> *your* point of view) that gave a *better* value for >> the computuational complexity of string searching >> than any of the then known algorithms could provide. > > are you talking about KMP?
Yes. I cannot give you the source of the story, unfortunately, because I only have the *memory* of it but don't know exactly *where* I happended to read it. There, Knuth was said to have first analyzed the theoretical argument very, very carefully to figure out *why* it was that the theoretical bound was so much better than all "practically known" algorithms. It was by studing the theoretical work on computational complexity *only* that the light dawned upon him. (But of course, Knuth is "an uncreative dumbo fit only for production work" - I am speaking ironically here, which should be obvious.) > I'm not sure that's really a good example of > how useful "theoretical work" really is in practice: Oh sure, yes, yes, it is. But my problem is to find a good source of the original story. Maybe one of the readers of this thread can provide it? > the "better" computational complexity of KMP has > turned out to be mostly useless, in practice. Well, that's how things might turn out in the long run. Still, at the time, to all appearances, it *was* a case of practical creativity *triggered* by apparently purely theoretical work in complexity theory. More interesting than your trying to shoot down one special case of the more general phenomenon of theory engendering creativity would be to know your position on the more general question... It happens *often* in physics, you known. Einstein is only one example of many. Pauli's prediction of the existence of the neutrino is another. It took experimentalists a great deal of time and patience (about 20 years, I am told) until they could finally muster something amounting to "experimental proof" of Pauli's conjecture. Regards, Christian -- "Experience without theory is blind, but theory without experience is mere intellectual play." - Immanuel Kant »Experience remains, of course, the sole criterion of the *utility* of a mathematical construction. But *the*creative*principle* resides in mathematics.« - Albert Einstein: The World As I See It »The astronomer Walter Baade told me that, when he was dining with Pauli one day, Pauli exclaimed, "Today I have done the worst thing for a theoretical physicist. I have invented something which can never be detected experimentally." Baade immediately offered to bet a crate of champagne that the elusive neutrino would one day prove amenable to experimental discovery. Pauli accepted, unwisely failing to specify any time limit, which made it impossible for him ever to win the bet. Baade collected his crate of champagne (as I can testify, having helped Baade consume a bottle of it) when, just over twenty years later, in 1953, Cowan and Reines did indeed succeed in detecting Paulis particle.« - Fred Hoyle: Astronomy and Cosmology
-- http://mail.python.org/mailman/listinfo/python-list
