Lynn H. Maxson
Fri, 30 Jun 2000 08:04:16 -0700 (PDT)
Jason Marshall wrote:"...Unless it is provably
impossible for a particular direction to contain a
successful 'hit', then you're using a heuristic,
and no longer doing an exhaustive search."
I don't know why this provides such concern.
Fortunately this is not my invention but one which
has developed over the years in AI logic engines.
I don't know if we are in sync with respect to
"heuristic", but certainly with respect to
"directed search". Allow me to offer an example.
Spiders have 8 legs. Beetles have 6. I have a box
containing spiders and beetles. In performing a
count I come up with 46 legs. Now the question is
how many beetles and spiders are in the box?
The logical expression for this is:
8s + 6b = 46. Now to set the conditions. The
number of spiders or beetles must be equal to or
greater than zero.
Now the fact is that the number of spiders cannot
exceed 5, and the number of beetles 9. Thus the
results for each must lie between 0 and 5 for the
spiders and 0 and 9 for the beetles. The resultant
set of values (as there are two valid solutions)
must lie with this range.
Now there are probably other ways I could instill
"clever" logic, logic that I would use to avoid
"brute force" on my part and that I was willing to
transfer to the software so that it could avoid it
on its part.
Now this probably falls under your category of a
"directed search". I have no argument with that.
In turn it produces the same result as an
"exhaustive search" using "brute force". They are
then "logically equivalent". Certainly it is
provably impossible for upper limit values above
the calculated ones to provide a "successful hit".
Now this example comes straight from Trilogy, a
DOS-based product (1988) written by a professor of
mathematical logic, Paul Voda, now in a university
in Slovakia. This product is based on predicate
logic which as you know means "For any..." or "For
every...". The part I inserted about the upper
limits is part of the setup or evaluation process
encoded within its logic engine.
In your terms it is a directed search. I agree.
In my terms it is "logically" the same "as if" an
exhaustive search had taken place. In that sense
it satisfies the exhaustive true/false proof
process of logic programming.
I am in no mood to "scold" someone about "truth in
advertising" if no deception has occurred. It
seems to me that this form of "self-examination" to
avoid doing the unnecessary falls well within the
scope of "reflective programming".
Certainly the ability to express "for s and b
greater than 0 and n = 46, determine s,b when 8s +
6b = 46", knowing full well that the results will
return 0, 1, or more "true" instances. Now in
logic programming this expression is treated as an
assertion. Rather than prove that it is true, they
take the tack of proving that it is false. To show
that it is false they (logically) enumerate all
possible value sets and test each one. If every
test fails, then they return 0 (false), otherwise
they return the true instances.
Not surprisingly this 0, 1, or more is a "piece of
cake" in list processing languages like Lisp. For
that reason many of the first AI expert systems
were written in Lisp. In fact as this lies at the
"core" as it were of Prolog, many of the first
Prolog compilers were written in Lisp.
If we rewrite our spider and beetle assertion as
8s + 6b = n, note that for a given range of values,
say (n,s,b) => 0 & =< 100 we can solve for all
possible value sets of (n,s,b): three unknowns. As
in our problem, in which we took only one
possibility, we can solve for 2 unknowns (with one
given): (s,b), (s,n), (b,n). Or for 1 unknown
(with two givens): (s), (b), (n). Or for 0
unknowns: true, false.
Furthermore we can use specific values, ranges of
values, lists of values or value sets. The set up
to the logic engine is the same. It establishes
the "stated" conditions plus some of its own to
avoid "provably unnecessary" tests and rearrange
the equation to a logical equivalent for the
particular type of solution desired in terms of
givens and unknowns.
Now frankly I like the idea of having a single
expression which I can invoke with any of these
"condition sets". I, as the user, don't have to
worry about "how" it is done. I only have to know
"what" I want done.
If you look at it, the form is quite close to what
the user would have used in his algebra course. If
he saw it with the conditions, it would look
familiar to him. He would understand "what"
happens even if he unsure "how" to make it happen.
"Any commentary regarding the rest of your comments
hinges on the formal definitions, so I'll hold off
on any commentary."
Well, don't hold back.<g> Admittedly they are
preliminary and need a little work.<g>