Proposals

[Lynn H. Maxson]

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>