John McCarthy has died. The great John McCarthy. Brilliant and entertaining, fun to be around, accessible unlike many of his stature, who carried an aura about him which blessed you with the feeling, if you came within it, that you were doing the Thinking That Really Mattered. Even if you were just flapping around at a loss for ideas.
The German Wikipedia describes him as a logician and computer scientist. The English version as a computer scientist and cognitive scientist. The German has it right.
John used to be quite happy to get in discussions with everyone about anything and became well known for it as Internet news groups really got started in the mid-1980’s. He had a knack for posing simple questions that turned out to be hard to answer.
And not just in AI. For example, check out his proposal for a new civil right on what counts for him as his personal page:
Remark: Ideally one would put all the information that one considers public about oneself on a page like this. When asked to fill out a form, one would simply put down the URL in place of any information that is on the page and tell the recipient of the form to just look it up.
One step beyond that is that any program needing this public information would just take it from the somewhat standardized web page.
More precisely, here’s a proposed new civil right. No Government agency, educational institution or business should ever be able to require anyone to supply anew information that the institution already has or is publicly available.
Typically for John, it is simple, doable, but somehow not done, and has significant social consequences. Let’s consider it a little further.
There are inadvertent violations. I tried to hand in a technical review of a paper submitted to an IEEE Transactions to the IEEE ScholarOne “system” (I use the word loosely) and found it wouldn’t let me do it without requiring me to fill in a lot of personal information. (I sent the review by email, and someone else has now tweaked the system enough to let me file, apparently.)
But the phenonemon is also used – and this, I suspect, is an insight of John – for political purposes. I had been asked on five or six occasions in the last year by a grant-supported institution with which I am associated to deliver information about activities (publications and talks and so on). Always the same stuff, but somehow not in quite the right format, or not quite the right selection. I began to suspect that someone is looking for a “reason” to ease me out, and so it turned out. Bureaucracy-overload as a political instrument; and of course always deniable.
The focus of this institution is, well, the successor “discipline” (I use the word loosely) to AI. John would have loved it!
Jon Hind informed a mailing list on Tuesday 25th October of the Guardian obituary that had just come out. There is a joint obituary with Dennis Ritchie in The Economist which appeared in the Novermber 5th print edition.
The Economist suggests that John did not suffer fools gladly. That is not quite how it was, as I recall. He engaged with all sorts of people – students mouthing off on Internet bulletin boards, for example, which nobody else did at the time. But he didn’t condescend. Anyone could talk to and argue with John, but he didn’t adjust his intellect to your capabilities – you had to adjust yours to his; for almost everyone an impossibly tall order. As well as being exactly what bright Stanford students need.
The Guardian article seems to me to miss most of what John was about during the 1980’s and 1990’s (the Economist, unusually, even more). Of course, after the invention of LISP, still the longest living programming language with over half a century of use (C, eleven years its junior, still has to catch up), one could regard anything else as a coda. But it was just a start. I’ll talk about the decade I know about, from the mid-1980’s to the mid-1990’s.
John had discovered, or invented, the Frame Problem, with Pat Hayes, and then came up with the cleanest purely technical proposal for solving it, Circumscription. Unfortunately, Circumscription didn’t turn out to solve the Frame Problem sui generis, but it did start a little industry all of its own. This little industry frustrated people such as Danny Bobrow, then-editor in the 1980’s of the premier journal in the field, Artificial Intelligence. Danny is a programmer through and through, who feels that to do AI you have to build stuff, that is, to program. The Circumscription industry consisted of a largish collection of mostly ex-Eastern European logicians, many of them eminent and all of them both capable and productive, who wrote great technical papers in mathematical logic and sent them to the Artifical Intelligence journal- where of course they had to be sent off to be refereed by other members of the group, and they took over about the third of the journal with all that ***** Math!! All good stuff no doubt, but it didn’t seem to some as if much was getting built………
It mirrored a significant split in AI, indeed in all computer science, which continues to this day. There are people who incline to solve problems intellectually before they solve them practically, and there are people who attempt practical solutions and solve, or resolve, issues as they come up to them. In AI in the 1980’s, they were known respectively as “neats” and “scruffies”. The neats have it right in that you cannot program solutions you do not have. The scruffies have it right in that a computational solution to a problem consists in an implementation. You might imagine that they could agree on a division of labor, but research is a little messier than that. The neats have it wrong in that abstraction is also a fine way of subtly changing the problem to fit the solution you happen to have, and the scruffies have it wrong in that a clever programmer can build wonderful programs which fail to solve the problem they set themselves, but “almost” do – the permanent, ineffable “almost”, which turns out to mean “never”.
John’s view on progress was that you knew a field was technically mature when you couldn’t understand the work of someone working on a different problem from you. Let’s turn that on itself. In some sense the division of AI research into neats and scruffies, say Danny’s frustrated view of all that math, could thereby have constituted a proof of some sort of maturity, although the way the squabbles were conducted left many wondering if that was the word for it! Maybe that was John’s point?
And John was the living contradiction to this view on progress. Of course. He could explain to anyone with a modicum of understanding of propositional calculus exactly what he was interested in and what problems he thought were worth solving. Check it out at his group WWW site. They were all so simple! Until you realised that, John being John, if they were really as simple as they looked, he would have solved them already. I recall one evening after dinner at the IJCAI conference in Detroit in 1989 when a bunch of us formal people were chatting away after late dinner. Along comes John. Says, “you know, I was thinking about this…… do you know how to do it?” and posed, as usual, what appeared to be a simple problem in propositional logic. Well, after a few minutes, everyone else made their excuses and left. I couldn’t solve it. Then came another problem. And another. All simple, all propositional logic, all needing to be solved if machines were going to mimic human decision capabilities. And, of course, AI meant that machines should be able to do this, somehow, so even if you programmed them with genetic algorithms or neural-network problem solvers, they would still just have been solving John’s “easy” problems in propositional logic. Surely a problem posed in logic can be solved in logic? Well, sometimes.
This went on for an hour and longer. At such sessions one could choose to feel stupid and frustrated at not being able to solve anything, or to revel in the creativity exhibited before your very eyes. For anyone can solve problems, but very, very few people know how to ask exactly the right questions. John was one. Astonishing performances, puzzles rolling off his tongue as if he were discussing the bus timetable. Anyone – and there were many – who claimed that “symbolic AI” was dead just hadn’t been listening properly. Symbolic AI wasn’t and isn’t “dead”. John’s simple problems need to be solved one way or another. But no longer by him, unfortunately.
Circumscription? Let me have a go. Circumscription is a syntactic (and therefore computationally feasible) way of doing the following. Say you have a description of part of the world in front of you, and what is going on in it. Say your description is in some language which allows deductive inference. Circumscription is a way of drawing rich inferences about features (“predicates”) of that scenario under the supposition that the world doesn’t have anything else in it but those objects expressly described plus whatever else needs to be there for the description to be accurate. Not just rich inferences, more than you could obtain with deduction alone, but rich, correct inferences. To logicians, it is a set of inference rules about what is true in certain minimal models of the set of sentences.
That is logically very important. Modern logic arose with Frege considering the logic of arithmetic, of counting and adding and so on. But in Frege’s logic, it turns out that you can’t just restrict your talk to the positive whole numbers. Circumscription was a way of trying to do just that for “worlds” which had a finite number of objects in them. It resolves many of the issues in the Frame Problem (maybe more appropriately called the Framing Problem), by implicitly defining what you are framing. However, it doesn’t neatly resolve the conundrum posed in 1986 by Steve Hanks and Drew McDermott and known as the Yale Shooting Problem. That was first resolved by using other principles. The conundrum it posed has now dropped out of fashion, as far as I know.
To see the rich the tradition around Circumscription, one may look at the Stanford Encyclopedia of Philosophy entries on Non-Monotonic Logic, on Defeasible Reasoning, on Logic and Artificial Intelligence, on the Frame Problem, on Ceteris Paribus laws (that is, rules based on “all other things being equal”).
John was not concerned merely with mimicking intelligence with machines, but with the more elusive reasoning phenomenon of common sense, which occurred in the title to a collection of his papers in 1990. There was a whole branch of AI research devoted to “common-sense” reasoning about the world; which in turn spawned a branch of reasoning called Qualitative Physics: how the world works ; check out for example this book chapter by Ken Forbus. (John, though, would have distinguished common-sense physics from qualitative physics.) If you put a round ball on a slanting table, it will roll down the slope and drop off the edge and hit the floor just beyond the edge, and how far beyond depends largely on its speed relative to the table when it drops. This phenomenon is known to every two-year-old a couple of decades before they can understand the Newtonian version, but we adults have far more trouble getting a handle on the qualitative reasoning than we do on Mr. Newton’s mathematics. Yet another delicious irony.
And one could go on. Maybe without end. Qualitative physics will not end; it’s a phenomenally hard problem. It may go out of fashion, but it’ll come back. And somebody will have to solve all those common-sense physics problems as well, and maybe differently. Circumscription didn’t solve the Yale Shooting Problem, but it did open up the study of rigorous forms of defeasible reasoning.
And always there was an irony, a delightful little joke in the tail. Somehow, you never quite knew whether you were thinking about a new subject or an elaborate joke. Look closely at the picture in the Guardian. Can you, also, maybe, see the slight smirk that I always thought I saw? Maybe, just maybe, AI was his very biggest joke of all…..