A Procedure for Thinking - Thinking as Computation - page 38

It is clear that there is a problem here. In trying to establish fido is a dog , the first
thing the procedure tries is to establish fido is a poodle . Not unreasonable. But instead
of the subquery's failing (as it should so that collie can be tried next), the procedure
finds the last sentence in the knowledge base and tries fido is a poodle again as a
subquery. It is stuck in a loop. It keeps trying to establish fido is a poodle over and
over. Consequently, the back-chaining continues forever and never returns success as
it should. Therefore, back-chaining is not logically complete.
What caused the problem here was the odd sentence saying that anything that is a
poodle is a poodle. Even though the sentence is true, it does not add anything to the
knowledge base. (The technical term is that the sentence is a tautology .) So one might
say that this odd sentence should never have been included in the KB and that back-
chaining is not to blame for the procedure's getting stuck. This is not an unreasonable
position. However, back-chaining can also get stuck on sentences that are not quite so
odd, so care will be needed to avoid this undesirable behavior.
Want to read more?
This chapter looked at a computational procedure whose inputs were sentences and
whose output was success or failure , according to whether an input sentence, called the
query, was logically entailed by a separate collection of sentences, called the knowl-
edge base. It is a simple matter to get a computer to perform this logical computation
in Prolog (see chapter 3).
Logic itself has a long history that in Western culture goes back to the ancient
Greeks. The modern form of symbolic logic is due to Gottlob Frege, with a specific
notation due to Giuseppe Peano, in the early 1900s. The motivation for this devel-
opment was the desire to put all of mathematical reasoning on a sound footing. In
the mid 1930s, Kurt G odel was able to prove in his celebrated Incompleteness Theo-
rem that this project was doomed, and that mathematical truth (in fact, even simple
arithmetic) had to go beyond the application of formal logical rules.
G odel was a genius. But his work, like that of his good friend Albert Einstein,
is perhaps outside the reach of beginners. Fortunately, there is a wonderful review
of this part of the history of logic in comic book form [13] that anyone can read
and enjoy. (Introductory textbooks on modern symbolic logic do exist, including at
least two outstanding ones [14, 15], but they necessarily assume some facility with
mathematics.)