Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.2 9/18/84; site ucbvax.ARPA Path: utzoo!watmath!clyde!cbosgd!ihnp4!ucbvax!RESTIVO@SU-SCORE.ARPA From: RESTIVO@SU-SCORE.ARPA Newsgroups: net.lang.prolog Subject: PROLOG Digest V3 #10 Message-ID: <5640@ucbvax.ARPA> Date: Wed, 20-Mar-85 07:59:48 EST Article-I.D.: ucbvax.5640 Posted: Wed Mar 20 07:59:48 1985 Date-Received: Thu, 21-Mar-85 04:03:12 EST Sender: daemon@ucbvax.ARPA Organization: University of California at Berkeley Lines: 261 From: Chuck Restivo (The Moderator) 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 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 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 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 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 ********************