Circumscription: a logical farce

Giant Arambourgiania pterosaurs arguing over a small theropod

Arambourgiania philadelphiae (CC) Mark Witton

Reality is unboundedly complex. Our knowledge of it is limited; in any practical situation, there are many relevant factors we are ignorant of. This creates deep problems for systematic rationality.

During the 1980s, I was involved in two different approaches to these difficulties. One was the logicist program in artificial intelligence, developed by John McCarthy, a founder of the field overall. McCarthy concluded that standard mathematical logic could not address problems of incomplete knowledge. He and others developed alternative, non-monotonic logics for the purpose. McCarthy called his version “circumscription.” His motivating example was the missionary and cannibals problem, a famous logical puzzle.

Logicism was opposed by Marvin Minsky, another founder of the field. I was a student of Minsky’s, and found his arguments against logicism convincing. But he didn’t have a coherent alternative.

By the mid-1980s, numerous serious obstacles in logicism became apparent, and the approach stalled. One was the Yale Shooting Problem, due to Drew McDermott, which showed that circumscription doesn’t work in general. McDermott, originally a student of Minsky, had switched to the logicist program, but in 1987 wrote a famous “Critique of Pure Reason,” arguing that the approach had failed.

Around the same time, Phil Agre and I developed an alternative approach, influenced by ethnomethodology, the empirical study of practical action, which we learned primarily from Lucy Suchman.

A year ago, I started work on In the Cells of the Eggplant, a book about how to better use systematic rationality. It draws on what I came to understand in the 1980s about reasoning with incomplete knowlege. Since last October, my time has been taken up with family responsibilities, so I only began writing again a few weeks ago.

I have an unfortunate weakness for intricate, absurdist jokes. They make some of my most important essays unnecessarily difficult to follow. I want The Eggplant to be as accessible as possible, so I keep removing jokes that might entertain some readers at the price of confusing most.

“Kill the kittens” is one of the best pieces of writing advice: remove anything you think is especially clever, that you are particularly fond of. It’s bound to be self-indulgent nonsense. The following explanation of circumscription is an extreme case. It belongs on the cutting room floor. And certainly not in the book! But I find it so cute that I can’t bear not to publish it as a blog post.

Couple more things to know before we get started. Dakinis are Buddhist witches, sometimes described as cannibals, and known sometimes for their lustful appetites. And, the victim in the Yale Shooting Problem was named Fred. McDermott thought Fred was a turkey, but he may have been mistaken.

text separator

[MARVIN and JOHN are conversing on a river bank. LUCY and PHIL are standing off to one side. She is videotaping their conversation, and he is taking notes on a clipboard.]

Marvin: You know the missionary and cannibals problem?

John: Let us suppose, for the sake of this imaginary conversation, that I do not.

[Enter the CHORUS: three monks pursued by three dakinis.]

Monks, singing the Strophe: We three monks wish to cross this great expanse of water, to preach the Holy Dharma in the lands beyond. Alas, yonder raft can carry only two people.

John: Easy! Two of you go across, one comes back on the raft, picks up the other, you both cross to the far side, and you leave the raft behind.

Monks: Alas, we take our religious vows extremely seriously. Especially the one about… women.

Dakinis, singing the Antistrophe: We three dakinis could not help noticing that these monks look mighty… tasty. We’d surely like to… eat them.

Monks: No no! You must not… eat us!

Dakinis: If, at any time, on either bank, we outnumber the monks, they will not be able to resist our charms.

Monks: To maintain our vows, the number of monks on either bank must be equal to, or greater than the number of dakinis.

Dakinis: We also must cross the river, to continue our pursuit.

Monks: So, the problem is: what is the smallest number of raft trips that will get us all across the river, with no vow breakage?

Lucy: This is ridiculous.

Phil: And offensive.

John: In a moment, I will show how to formalize this classic puzzle in mathematical logic. But first, the informal solution. Uh… let’s see… 1. Two dakinis cross, leaving one with three monks on this side. 2. Then one dakini returns and picks up the remaining dakini and 3. takes her to the far bank. Now all the dakinis are on the far bank. 4. One dakini returns. 5. Two monks cross, and—

Marvin: Wrong! The answer is: zero.

John: … Zero?

Marvin: All the monks and dakinis can just walk over the bridge together.

John: You didn’t say there was a bridge!

Lucy: You didn’t look! It’s right in front of you!

Marvin, ignoring her: I didn’t say there wasn’t a bridge. You just invented this non-bridgeness out of thin air. You had no evidence for it, and no logical justification.

John: You should have told me! This isn’t a fair problem.

Phil: Life is complicated. There’s always lots of things you don’t know—and don’t know you don’t know.

Lucy: Although, you could look.

John: This is ridiculous. There’s no such thing as “non-bridgeness.” And you might as well say there could be a giant pterosaur that would carry everyone across.

Phil: Well, that would be ridiculous. However, realistic possibilities are still effectively infinite.

Lucy: You can’t plan for most of them. You have to improvise.

John: Any rational person would agree that I was solving the problem as stated. It’s implicitly implied that there’s no bridge. The general principle is: anything that isn’t explicitly stated, can be assumed to be false. I shall call this “circumscription.” It’s a vital extension to formal logic, to make it usable when you have incomplete knowledge.

Applied to action, we will assume that nothing changes unless we have knowledge that it will. We can call this “logical inertia.” When two of the Chorus cross the river on the raft, we can infer that the other four stay put, although that is not explicitly stated.

More generally, circumscription formalizes Occam’s Razor. When there are alternate possible explanations, it chooses the one that minimizes the number of violated assumptions.

[Enter DREW with a musket.]

Drew: Unfortunately, that won’t work.

John: Why not?

Drew, loading the musket: Because simply minimizing the number of violated assumptions does not always yield a unique solution, and the correct one may not even be among the minima.

Phil: Also, because there is, in fact, a bridge. The original reason to introduce circumscription was to logically infer that there isn’t one, which—

Lucy: LOOK OUT!

[FRED, a giant pterosaur, swoops down. Drew shoots at him, but Fred is unharmed. Fred circles back and carries all the monks and dakinis across the river.]

John: You missed!

Drew: My aim is true.

Fred, returning and settling beside them: Fortunately, the bullet fell out of the musket while you were all distracted by a giant pterosaur.

John: It’s logical to assume that the gun stayed loaded, and circumscription allows us to infer that.

Fred: It’s also logical to assume I stayed alive.

John: But we have explicit knowledge that Drew shot at you, which we should logically assume led to your death. Two against one!

Drew: But, as I was explaining before we were interrupted by a giant pterosaur, simply counting the number of assumptions doesn’t give correct results in all cases. What we need is a theory of causality, and circumscription doesn’t give you that. Look, let’s write out the formulae on a, um, whiteboard…?

[Fred offers a wing to write on. Marvin, John, and Drew continue their good-natured debate, as old friends do.]

Phil, to Lucy: You got this all on tape?

Navigation

You are reading a metablog post, dated June 3, 2018.

The next metablog post is How should we evaluate progress in AI?.

The previous metablog post was Post-apocalyptic life in American health care.

This page’s topics are History of ideas and Rationalism.

General explanation: Meaningness is a hypertext book (in progress), plus a “metablog” that comments on it. The book begins with an appetizer. Alternatively, you might like to look at its table of contents, or some other starting points. Classification of pages by topics supplements the book and metablog structures. Terms with dotted underlining (example: meaningness) show a definition if you click on them. Pages marked with ⚒ are still under construction. Copyright ©2010–2018 David Chapman.