Comparing lists

[Christian Stapfer]

"Fredrik Lundh" <fredrik at pythonware.com> wrote in message
news:mailman.2137.1129475887.509.python-list at python.org...
> 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 Pauli’s particle.«
 - Fred Hoyle: ‘Astronomy and Cosmology’