marcel@uiucdcs.UUCP (marcel ) (12/28/83)
#N:uiucdcs:29700014:000:3810
uiucdcs!marcel Dec 27 16:08:00 1983
Here's a problem I'd like some comments on. If you can solve it, please
mail me your solution; if you can't, please let me know why you found it
impossible. First I'll present the problem (of my own devising), then my
comments, for your critique.
Suppose you are shown two lamps, 'a' and 'b', and you
are told that, at any time,
1. at least one of 'a' or 'b' is on.
2. whenever 'a' is on, 'b' is off.
3. each lamp is either on or off.
WITHOUT using an exhaustive generate-and-test strategy,
write a Prolog program to enumerate the possible on-off
configurations of the two lamps.
If it were not for the exclusion of dumb-search-and-filter solutions, this
problem would be trivial. The exclusion has left me baffled, even though
the problem seems so logical. Check me on my thinking about why it's so
difficult.
1. The first constraint (one or both lamps on) is not regular Horn clause
logic. I would like to be able to state (as a fact) that
on(a) OR on(b)
but since regular Horn clauses are restricted to at most one positive
literal I have to recode this. I cannot assert two independent facts
'on(a)', 'on(b)' since this suggests that 'a' and 'b' are always both
on. I can however express it in regular Horn clause form:
not on(b) IMPLIES on(a)
not on(a) IMPLIES on(b)
As it happens, both of these are logically equivalent to the original
disjunction. So let's write them as Prolog:
on(a) :- not on(b).
on(b) :- not on(a).
First, this is not what the disjunction meant. These rules say that 'a'
is provably on only when 'b' is not provably on, and vice versa, when in
fact 'a' could be on no matter what 'b' is.
Second, a question ?- on(X). will result in an endless loop.
Third, 'a' is not known to be on except when 'b' is not known to be on
(which is not the same as when 'b' is known to be off). This sounds as
if the closed-world assumption might let us get away with not being able
to prove anything (if we can't prove something we can always assume its
negation). Not so. We do not know ANYTHING about whether 'a' or 'b' are
on OR off; we only know about constraints RELATING their states. Hence
we cannot even describe their possible states, since that would require
filling in (by speculative hypothesis) the states of the lamps.
What is wanted is a non-regular Horn clause, but some of the nice
properties of Logic Programming (eg completeness and consistency under the
closed-world assumption, alias a reasonable negation operator) do not apply
to non-regular Horn clauses.
2. The second constraint (whenever 'a' is on, 'b' is off) shares some of the
above problems, and a new one. We want to say
on(a) IMPLIES not on(b), or not on(b) :- on(a).
but this is not possible in Prolog; we have to say it in what I feel to
be a rather contrived manner, namely
on(b) :- on(a), !, fail.
Unfortunately this makes no sense at all to a theoretician. It is trying
to introduce negative information, but under the closed-world assumption,
saying that something is NOT true is just the same as not saying it at all,
so the clause is meaningless.
Alternative: define a new predicate off(X) which is complementary to on(X).
That is the conceptualization suggested by the third problem constraint.
3. off(X) :- not on(X).
on(X) :- not off(X).
This idea has all the problems of the first constraint, including the
creation of another endless loop.
It seems this problem is beyond the capabilities of present-day logic
programming. Please let me know if you can find a solution, or if you think
my analysis of the difficulties is inaccurate.
Marcel Schoppers
U of Illinois at Urbana-Champaign
{pur-ee|ihnp4}!uiucdcs!marcelMarcel%Ucb-Vax@uiucdcs.UUCP (12/28/83)
Here's a problem I'd like some comments on. If you can solve it,
please send this Digest your solution; if you can't, please let
me know why you found it impossible. First I'll present the
problem (of my own devising), then my comments, for your critique.
Suppose you are shown two lamps, 'a' and 'b', and you
are told that, at any time,
1. at least one of 'a' or 'b' is on.
2. whenever 'a' is on, 'b' is off.
3. each lamp is either on or off.
Without using an exhaustive generate-and-test strategy,
write a Prolog program to enumerate the possible on-off
configurations of the two lamps.
If it were not for the exclusion of dumb-search-and-filter
solutions, this problem would be trivial. The exclusion has
left me baffled, even though the problem seems so logical.
Check me on my thinking about why it's so difficult.
1. The first constraint (one or both lamps on) is not regular
Horn clause logic. I would like to be able to state (as a
fact) that
on(a) OR on(b)
but since regular Horn clauses are restricted to at most one
positive literal I have to recode this. I cannot assert two
independent facts 'on(a)', 'on(b)' since this suggests that
'a' and 'b' are always both on. I can however express it in
regular Horn clause form:
not on(b) IMPLIES on(a)
not on(a) IMPLIES on(b)
As it happens, both of these are logically equivalent to
the original disjunction. So let's write them as Prolog:
on(a) :- not on(b).
on(b) :- not on(a).
First, this is not what the disjunction meant. These rules
say that 'a' is provably on only when 'b' is not provably
on, and vice versa, when in fact 'a' could be on no matter
what 'b' is.
Second, a question ?- on(X). will result in an endless loop.
Third, 'a' is not known to be on except when 'b' is not known
to be on (which is not the same as when 'b' is known to be off).
This sounds as if the closed-world assumption might let us get
away with not being able to prove anything (if we can't prove
something we can always assume its negation). Not so. We do not
know Anything about whether 'a' or 'b' are on OR off; we only
know about constraints Relating their states. Hence we cannot
even describe their possible states, since that would require
filling in (by speculative hypothesis) the states of the lamps.
What is wanted is a non-regular Horn clause, but some of the
nice properties of Logic Programming (e.g. completeness and
consistency under the closed-world assumption, alias a reasonable
negation operator) do not apply to non-regular Horn clauses.
2. The second constraint (whenever 'a' is on, 'b' is off) shares
some of the above problems, and a new one. We want to say
on(a) IMPLIES not on(b), or not on(b) :- on(a).
but this is not possible in Prolog; we have to say it in what I
feel to be a rather contrived manner, namely
on(b) :- on(a), !, fail.
Unfortunately this makes no sense at all to a theoretician. It
is trying to introduce negative information, but under the
closed-world assumption, saying that something is Not true is
just the same as not saying it at all, so the clause is
meaningless.
Alternative: define a new predicate off(X) which is complementary
to on(X). That is the conceptualization suggested by the third
problem constraint.
3. off(X) :- not on(X).
on(X) :- not off(X).
This idea has all the problems of the first constraint, including
the creation of another endless loop.
It seems this problem is beyond the capabilities of present-day
logic programming. Please let me know if you can find a solution,
or if you think my analysis of the difficulties is inaccurate.
-- Marcel Schoppers
Univ. of Illinois at Urbana-Champaign
CSNet: {pur-ee|ihnp4}!uiUUCDCS!Marcel