YKY (Yan King Yin) wrote:
I have the intuition that Levin search may not be the most efficient
way to search programs, because it operates very differently from
human programming. I guess better ways to generate programs can be
achieved by imitating human programming -- using techniques such as
deductive reasoning and planning. This second method may be faster
than Levin-style searching, especially for complex
programming problems, yet technically it is still a search algorithm.
My questions are:
Is deductive-style programming more efficient than Levin-search?
If so, why is it faster?
YKY
------------------------------------------------------------------------
Deduction can only be used a very constrained circumstances. In such
circumstances, it's exponentially slow (or super-exponentially?) with
the number of cases to be handled.
I don't know anything about Levin searches, but heuristic searches are
much faster at finding things in large search spaces than is deduction,
even if deduction can be brought to bear (which is unusual).
OTOH, if deduction can be brought to bear, then it is guaranteed to find
the most correct solution. Heuristic searches stop with something
that's "good enough", and rarely will do an exhaustive search.
That said, why do you think that people generally operate deductively?
This is something that some people have been trained to do with inferior
accuracy. I still don't know anything about Levin searches, but people
don't search for things deductively except in unusual circumstances, so
that it's not deductive is not saying that it doesn't do things the way
that people do. (I think that people do a kind of pattern
matching...possibly several different kinds. Actually, I think that
even when people are doing something that can be mapped onto the rules
of deduction, what they're actually doing is matching against learned
patterns.) One reason that computers are so much better than people at
logic is that that's what they were built to do. People weren't and
aren't. But whenever one steps outside the bounds of logic and math,
computers really start showing how little capability they actually have
compared to people. But computers will do what they are told to do
with incredible fidelity. (Another part of how they were designed. So
they can even emulate heuristic algorithms...slowly. You just don't
notice most of what you are doing & thinking. Only a small fraction
that can easily be serialized (plus a few random snap-shots with low
fidelity [lossy compression?]).
-----
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/?member_id=8660244&id_secret=63993815-f7d737
