Eric Baum wrote:
Matt wrote:
Anyway, my point is that decoding the human genome or natural language is n=
ot as hard as breaking encryption. It cannot be because these systems are =
incrementally updatable, unlike ciphers. This allows you to use search str=
ategies that run in polynomial time. A key search requires exponential tim=
e, or else the cipher is broken. Modeling language or the genome in O(n) t=
ime or even O(n^2) time with n =3D 10^9 is much faster than brute force cry=
ptanalysis in O(2^n) time with n =3D 128.
I don't know what you mean by incrementally updateable,
but if you look up the literature on language learning, you will find
that learning various sorts of relatively simple grammars from
examples, or even if memory serves examples and queries, is NP-hard.
Try looking for Dana Angluin's papers back in the 80's.
No, a thousand times no. (Oh, why do we have to fight the same battles
over and over again?)
These proofs depend on assumptions about what "learning" is, and those
assumptions involve a type of learning that is stupider than stupid.
Any learning mechanism that had the ability to do modest analogy
building across domains, and which had the benefit of primitives
involving concepts like "on", "in", "through", "manipulate", "during",
"before" (etc etc) would probably be able to do the grammer learning,
and in any case, the proofs are completely incapable of representing the
capabilities of such learning mechanisms.
Such ideas have been (to coin a phrase) debunked every which way from
sunday. ;-)
Richard Loosemore
-----
This list is sponsored by AGIRI: http://www.agiri.org/email
To unsubscribe or change your options, please go to:
http://v2.listbox.com/member/?list_id=303
