RESTIVO@SU-SCORE.ARPA (03/20/85)
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SU-SCORE.ARPA>
PROLOG Digest Wednesday, 20 Mar 1985 Volume 3 : Issue
Today's Topics:
Puzzles - Oliver's Confusion
Implementation - Tablog & Testing & Bounded Merge
----------------------------------------------------------------------
Date: 27 Feb 85 0913 PST
From: John McCarthy <JMC@SU-AI.ARPA>
Subject: Oliver problem
Companion to Concrete Mathematics, Z. A. Melzak, Wiley 1971.
sqrt(lambda x.x**2-2) = lambda x.[((x+sqrt(x**2-4))/2)**sqrt(2)
+ ((x-sqrt(x**2-4))/2)**sqrt(2). See p.54, example d.
------------------------------
Date: 8 Mar 1985 17:38-EST
From: Michael Restivo <MSR%SUNY-SBCS@CSNet-Relay>
Subject: Oliver's Puzzle
Q: "Can a computer solve the query:
"If f(f(x)) = x^2 - 2, what is f(x)?
If so, how?"
There is a closed form solution to a related problem.
That is, the forward problem:"if f(x) = x^2 - 2, what
is f(f(x))?"
Envision the following structure of composed functions.
x ----- f(x) ----- f(f(x)) ----- - - -
| | |
f0(x) f1(x) f2(x)
The solution involves the notion of conjugate functions
in order to arrive at the closed form solution from which
any such fi may be derived.
fn(x) = ((x + (x^2 - 4)^(1/2))/2)^(2^n) +
((x - (x^2 - 4)^(1/2))/2)^(2^n)
Moving forward then,
f2(x) = (15x^4 - 96x^2 + 272 - 256x^(-2))/8
Attaining a closed form solution is hard in general for the
forward problem. The backward problem is "given fj(x), what
is f1(x)?" This is Oliver's question. Can anyone suggest
a reference?
Z. A. Melzak, Companion to Concrete Mathematics: Mathematical
Techniques and Various Applications, J. Wiley & Sons, 1973.
Z. A. Melzak, Mathematical Ideas, Modeling & Applications:
Volume II of Companion to Concrete Mathematics, J. Wiley &
Sons, 1976.
------------------------------
Date: Tue 26 Feb 85 23:00:49-PST
From: Byrd@SRI-AI.ARPA
Subject: Testing for renamable-Horn sets
(Actually, this is Richard A. O'Keefe, using
Lawrence Byrd's account.)
Testing whether a set of clauses is renamable-Horn is indeed
a linear-time process. In hand-waving terms, the reason for
that is the set of renamable-Horn sentences is a very very
small fraction of the set of all sentences. But it is a
large fraction of the sets we are interested in. Note that
all renaming does is to replace P(args) by NOT P(args)
***uniformly***, and of course conversely. It turns out that
the key to doing this is to find a model for a certain set of
propositional clauses, each with precisely two literals, and
because of this very peculiar property (2 literals) it is
equivalent to finding a topological ordering on a certain
graph. Toplogical ordering is linear, the graph is at worst
quadratic in the number of predicate symbols, and the input
sentence dominates that. It is a similarly trivial exercise
to show that finding a model of a set of propositional Horn
clauses is linear in the size of the input sentence. This
does not, for obvious reasons, generalise to non-Horn sets.
I was suggesting searching for a renaming as a preliminary
filter; as a way of locating predicates that need a fuller
treatment. The Alpine Club example itself shows that you
will generally NOT find a renaming for the original sentence,
but that you may be able to find a renaming for a useful
chunk of it and use that as a way of handling "trivial"
negations.
One thing bothers me about an earlier proposed solution to
the Alpine Club problem, and that was the use of
likes(Person, not(Thing))
to mean that Person doesn't like Thing. A problem with
likes(john, not(sharks))
is that it doesn't match the question
?- likes(john, penguins)
and I really do not see how to interpret it at all.
------------------------------
Date: Tue 5 Mar 85 08:09:53-EST
From: Vijay <Vijay.Saraswat@CMU-CS-C.ARPA>
Subject: Negation,TABLOG etc.
Why can Prolog solve some problems using negation
in a reasonably natural fashion and not some others?
Well, I would claim that really Horn logic isn't the
right vehicle for having to deal with such problems;
if you can get by using the very weak negation as
failure rule, you should consider yourself lucky.
In these special cases (the Alpine Club problems)
where there are no function symbols, so that the
Herbrand domain is finite, trivially the greatest
fixedpoint of the usual transformation associated
with the program can be obtained by a finite number
of iterations; gfp(Tp)-T_w (where T_w represents is
ttyese for T-downarrow-omega) is empty, and hence
negation-as-failure is complete with respect to
negation in the IFF-completion of the theory. In
general, however it can be highly incomplete; refer
to Howars Blair's paper in Info and Control, v.54,
1982, pp 25-47.
As far as Richard O'Keefe's solution is concerned,
I contend that he cheats significantly, as far as
representing the equivalence between what Tony likes
and Mike dislikes is concerned. He must, in addition,
add the axioms:
likes(Tony, X, yes):- likes(Mike, X, no).
likes(Tony, X, no):- likes(Mike, X, yes).
thus causing the SLD-refutsation tree for the given
query to become infinite. Now whether Prolog finds
the finite successful path depends crucially on the
ordering of clauses. (Ofcourse using nonskier instead
of skier itself involves a tremendous bias in using
those rules!)
I would claim that if you did not know that Mike was
an answer (the only answer) to the alpine club problem
beforehand, it would be quite hard to get your axioms
looking just right for Prolog to find the answer the
first time around.
I have already indicated why it would be not possible
to cleanly formulate the revised Alpine Club problem
in Prolog: there does not exist a single individual
who is a witness in ALL MODELS for the given query.
Consequently, there can be no sequence of substitutions
on variables in the initial query which can give you
the answer. Consequently, the initial query must be
ground. But by the structure of the problem you know
that means it must have an embedded disjunction in it.
So what the hell are we doing in Horn logic anyway?
Which brings me to Tablog and related first order
language. I am not at all surprised that this
problem can be nicely formulated in it. What you
gain in expressive power by going to full first order
logic, you lose in the simplicity of your semantics.
Given any full first order logic logic programming
language it is difficult to give an answer to the
simplest question of them all: what is your model?
If your interpretation mechanism is a sound and
complete refutation procedure you are computing
exactly the first order logical consequences of the
given axioms. But that still does not help identify
the extensions of predicates in some fixed canonical
model, THE model of interest. That is what initial
models, which may not exist in the general case, allow
you to do in the Horn case. It is indeed quite beautiful
that the least fixed point interpretation of recursive
predicate definitions coincides with validity in all
models for a set of Horn axioms.
And then, of course, there is the problem that the
search space branches much more rapidly in the full first
order logic case, and so you have to introduce even more
control in order to write programs efficiently. The art
of designing a logic programming language is basically
concerned with finding that delicate balance between
expressibility and control which allows you to frame
your problems elegantly in a formalism so that the solution
space does not contain too many garden paths and giving
that information (i.e. of the useless paths to avoid) to
the execution mechanism does not obscure the logical
content of the program.
I will be really impressed by TABLOG when it contains a
useful and general means for the progammer to control
deduction at some level after he has written his axioms
and observed its behaviour on the inputs of interest.
Another simple observation: how does a programmer in
Tablog know that his 100,000 line program is logically
consistent? (In Horn logic he need not bother).
I think I still believe that if the knowledge at hand
is expressible in Horn terms, then a Horn logic programming
language is anyday superior to a more general purpose logic
progamming language. One of the reasons why Horn logic
programming has lasted so long, I think, is that it
captures exactly the kind of information that is generally
used for writing real-life programs: positive, definite
information.
Cheers.
-- Vijay.
------------------------------
Date: Mon 18 Mar 85 07:15:58-EST
From: Vijay <Vijay.Saraswat@CMU-CS-C.ARPA>
Subject: Shapiro's response to merge/5 and merge/7
Thanks to unpredictable time lags between inputs
from the Weizmann Instt. and from CMu to the Prolog
Digest, Shapiro's remarks on merge/5 and merge/7
not working with respect to original CP semantics
referes to a version of merge/5 and merge/7 which
was pulled from the Digest over two weeks ago
immediately after I realised this mistake. As
should be abundantly clear to anyone who has been
following this discussion, my note which appears in
the Digest just before Shapiros actually discusses
the possibility of merge/5 causing an input stream
to become a protected exported stream and shows
how to get around it by using copy/3 and equating
the two input channels.
To my knowledge the versions of merge/5 which
appear in the Prolog Digest are still correct,
given the different semantics of CP's ? they
deal with.
For my part, I would still prefer the ! annotation
as against the two or three versions of CP's ? that
have been discussed in the Prolog Digest.
-- Vijay.
------------------------------
End of PROLOG Digest
********************