Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!wuarchive!usc!randvax!narain
From: narain@randvax.UUCP (Sanjai Narain)
Newsgroups: comp.lang.prolog
Subject: Re: Hype about Prolog
Message-ID: <2554@randvax.UUCP>
Date: 25 May 90 18:18:11 GMT
References: <2550@randvax.UUCP> <21552@megaron.cs.arizona.edu>
Organization: Rand Corp., Santa Monica, Ca.
Lines: 21

Of course, the difficulty of reasoning about non-deterministic algorithms
depends upon the algorithm. What I said was that by expressing these
in logic, one can reason about them the same way as one reasons about
other sentences in logic. For example, it is quite easy to show that
the following non-deterministic program:

	subset([],[]).
	subset([U|V],Z):-subset(V,Z).
	subset([U|V],[U|Z]):-subset(V,Z).

will compute exactly 2**n subsets of a set of length n (represented as
a list), and whose complexity is O(2**n) SLD-resolution steps.

An interesting question is this: why is it that algorithmic knowledge
can be expressed using definite clauses, but not using full first-order
logic (at least in any obvious way)?

Other logics in which one can express algorithmic knowledge are
equational logic, lambda calculus, and combinatory logic.

Sanjai Narain