John McCarthy's Home PageJohn McCarthy's Home PageI'm Professor Emeritus (as of 2001 Jan 1) of Computer Science at Stanford University and here's more about me including addresses.
It occurs to me that those who have already looked at this web page might not want to slog through all of it on the chance that something newly installed might interest them. If you've looked at the page before, then look at this dated list. Dates start in 1995 July. I sometimes miss one or two.
THE ROBOT AND THE BABY is a science fiction story. Maybe I'll try to publish it conventionally. Do you think I should?
I have decided to make some comment from time to time on world, national and scientific affairs. I don't have time to make this into a proper blog.
INTRODUCTORY.My goal is get all my papers and many of my notes into a form reachable from this page.
Slides for most of my lectures are here.
If any of the papers here are listed as references, I would be grateful if the URLs were given along with the printed references. Some are available only as Web documents and will remain that way. Please include them as references if you would reference a printed document with the same content.
The Sustainability of Human
Progress
Many people, including many scientists, mistakenly believe that human progress,
in the form it has taken in the last few hundred years, is unsustainable. The
sustainabililty page and its subsidiaries attempt to summarize the scientific
basis for technological optimism. There is also a section discussing related
ideological phenomena and the advocacy politics to which ideologies have given
rise.
The sustainability pages are essentially done, although I plan to improve them and respond to inadequacies people find. Having done my best to show that material progress is sustainable, I can turn my attention to the future and present ideas about what progress people will want and what can be achieved. The emphasis is on opportunities rather than on inevitability.
Up to: The Formal Reasoning Group which has links to the pages of my associates and students.What is Artificial Intelligence? contains non-technical answers to some frequently asked questions.
Recursive Functions of Symbolic Expressions and their Computation by Machine (Part I). This was the original paper on LISP.
It is copied with minor notational changes from CACM, April 1960. If you want the exact typography, look there. A few typographical changes have been made, but the notation has not been modernized. There are also some new explanatory footnotes. Part II, which never appeared, was to have had some Lisp programs for algebraic computation.
LISP---NOTES ON ITS PAST AND FUTURE---1980 was published in 1980. I put it up since it mostly represents my present opinions. There are some 1999 footnotes.
Elephant 2000 - 1992
This unpublished draft is a proposal for a new programming language, but it
includes the mathematical theory of computation proposal for
distinguishing input-output and accomplishment specifications, characterizes
input and output statements as speech acts and allows reference to the past in
programs.
Towards a Mathematical Science of Computation, IFIPS 1962 extends the results of the previous paper. I think it is the first mention and use of abstract syntax.
Correctness of a Compiler for Arithmetic Expressions by John McCarthy and James Painter may have been the first proof of correctness of a compiler. Abstract syntax and Lisp-style recursive definitions kept the paper short.
@Book{McC90,
author = "John McCarthy",
title = "Formalization of common sense, papers by {J}ohn
{M}c{C}arthy edited by {V}. {L}ifschitz",
publisher = "Ablex",
year = "1990",
}
Inversion of Functions Defined by Turing Machines was included in Automata Studies edited by Claude Shannon and myself and published by Princeton University Press in 1956. It introduced the notion of well-defined problem, but I became convinced that inverting computable functions in general is not a feasible way of doing AI.
Programs with Common Sense was probably the first paper on logical AI, i.e. AI in which logic is the method of representing information in computer memory and not just the subject matter of the program. The paper was given in the Teddington Conference on the Mechanization of Thought Processes in December 1958 and printed in the proceedings of that conference. It may also be the first paper to propose common sense reasoning ability as the key to AI.
Some Philosophical Problems from the Standpoint of Artificial Intelligence by John McCarthy and Pat Hayes was published in 1969 in Machine Intelligence 4. It is the basic paper on situation calculus.
My 1964 Stanford AI Memo A Tough Nut for Proof Procedures has aroused increased interest lately. The present version has some recent comments. It is to prove that a checkerboard with two diagonally opposite squares removed cannot be covered by dominoes that cover two adjacent squares.
The Mutilated Checkerboard in Set Theory was presented at the QED meeting in Warsaw in 1995 July. It is a proof in set theory that I think an interactive prover for heavy duty set theory should be able to accept. It uses for a different purpose the same problem as the previous paper.
Circumscription - A Form of Nonmonotonic Reasoning was published in Artificial Intelligence in 1980.
Applications of Circumscription to Formalizing Common Sense Knowledge was published in Artificial Intelligence in 1986. It gives a better formulation of circumscription and emphasizes making certain functions and predicates variable.
Ascribing Mental Qualities to Machines concerns what it means for a machine to have beliefs. This started the dispute about whether thermostats could be considered to have beliefs. It was published in 1979 in an obscure collection and reprinted in my 1990 book Formalizing Common Sense.
First Order Theories of Individual Concepts and Propositions was first published in Machine Intelligence 9 in 1979.
Artificial Intelligence, Logic and Formalizing Common
Sense
in Philosophical Logic and Artificial Intelligence edited by Richmond
Thomason (Dordrecht ; Kluwer Academic, c1989).
This contains a reasonably up-to-date (even as of 1994) point of view of
logical AI. It doesn't cover what I don't know or have forgotten.
Notes on Formalizing Context
Appeared in Proceedings of IJCAI - 1993. This version
has an improvement in the way lifting above-theory is treated.
Formalizing Context (Expanded Notes) contains expanded material on context. It is joint work with Sasa Buvac.
Artificial Intelligence and Philosophy was given at Aaron Sloman's Symposium on philosophy and AI at IJCAI-95. The present version is somewhat improved.
A LOGICAL AI APPROACH TO CONTEXT responds to a request for a note on our approach to formalizing context in mathematical logic that can be compared with John Perry's situation semantics based approach to context. It will appear (presumably appeared) in a CSLI (Center for Studies in Linguistics and Information) publication.
Making Robots Conscious of their Mental States was given at Machine Intelligence 15, 1995 August in Oxford. It's in the Proceedings of that workshop. The idea is that many tasks will require the computer programs examine their own computational structures in ways like those involved in human consciousness and indeed self-consciousness. The present version is much improved.
Some Expert Systems Need Common Sense was published in 1984. Some people are re-defining AI in such a way that common sense and therefore human level AI are precluded. They do this inadvertently (presumably) by assuming that some human limits what phenomena are to be taken into account in defining the AI system.
Coloring Maps and the Kowalski Doctrine was a 1982 Stanford report. More is known about realizing the Kempe heuristic by making a Prolog that can run in an introspective mode, and I'll put in a note about it when I get a chance.
The Little Thoughts of Thinking Machines is a popular article that appeared in Psychology Today in 1983.
Epistemological Problems of Artificial Intelligence summarized the epistemological problems I saw at that time. It was an invited talk at IJCAI-77. Many of the problems mentioned in this paper were treated later in more detail by myself and other people.
Generality in Artificial Intelligence relates to my ACM Turing Award lecture given in 1971. However, the ideas didn't jell sufficiently at that time to be written up. In 1987 ACM asked for a summary to include in a volume of Turing Award lectures. Instead I wrote this complete paper. Its actual relation to the 1971 lecture is hard to say, since I didn't remember what I said in 1971.
On the Model Theory of Knowledge by myself, M. Sato, T. Hayashi and S. Igarashi was written in the late 1970s.
Creative Solutions to Problems was given at the AISB Workshop on Artificial Intelligence and Creativity, 1999 April 8 and 9.
Combining Narratives is by John McCarthy and Tom Costello. It was presented at KR-98 in Trento, Italy.
A major feature of this paper is that sentences describing two independent narratives can be combined just by conjoining the sentences. Sentences can be added later to establish relations between them.
Todd Moody's Zombies is an invited commentary that appeared in Volume 2, Issue 4 (1995) of the Journal of Consciousness Studies.Useful Counterfactuals by Tom Costello and John McCarthy is published in the ETAI (Electronic Transactions on Artificial Intelligence), Vol 3 (1999), Section A.
Counterfactual conditional sentences can be useful in artificial intelligence. In particular, they allow reasoners to learn from experiences that they did not quite have. The truth of a counterfactual and the conclusions that can be drawn from a counterfactual are theory dependent, and different theories are useful in different circumstances.
A simple class of useful counterfactuals involves a change of one component of a point in a space provided with a cartesian product structure. We call these cartesian counterfactuals. Cartesian counterfactuals can be modeled by assignment and contents functions as in program semantics. We also study the more general tree-structured counterfactuals.
Free Will - Even for Robots will appear in a special issue of the Journal of Experimental and Theoretical Artificial Intelligence devoted to philosophical questions. Robots will need to consider their own choices in a manner similar to that in which a human contemplates his own free will.
DETERMINISTIC FREE WILL is a shorter paper than Free Will - Even for Robots. I think it gets to the essence of free will and incorporates it in a situation calculus formula.
AI needs to deal with objects and predicates that don't admit if-and-only-if definitions. It also needs approximate theories and needs to study the relation between entities at different levels of approximation. Approximate objects and approximate theories is in the Proceedings of KR-2000.
ACTIONS AND OTHER EVENTS IN SITUATION CALCULUS
This is a new (2001 August) article on situation calculus. It differs from previous approaches in three ways. It distinguishes internal events that happen spontaneously from external events (actions). It also treats processes, e.g. a buzzer, that do not settle down. The non-monotonic reasoning is circumscription done situation by situation. It is in the Proceedings of KR-2002.
An Example for Natural Language Understanding and the AI Problems it Raisestry. - 1976. Apparently these problems haven't been solved and the recently popular statistical methods don't even try.
Overcoming unexpected obstacles is a note written in 1992 and 1993 describing an important kind of elaboration tolerance. A plan is shown to work by reasoning involving circumscribing a predicate occurs(e,s) asserting that the event e occurs in situation s. If a sentence is added asserting the occurrence of an event that defeats the plan and the circumscription is done again, the plan can no longer be shown to work. In our example, a revised plan including an action that overcomes the obstacle can be shown to work. There is a bug in handling the circumscription that I have not fixed, and this accounts for the long delay in posting this note.
Formalization of two Puzzles Involving Knowledge involves formalization of facts about knowledge including both knowing what and knowing that, how to assume and prove non-knowledge, joint knowledge and the effect of learning a fact on the set of facts then known. It uses the Kripke possible worlds formalism directly.
What is AI? is intended to answer questions I get in email from people uninformed about AI. Suggestions for improving it are welcome, and anyone who has a use for it is welcome to link to it or copy it.
Making Computer Chess a Drosophila for AI is an outgrowth of my review of Monty Newborn's Kasparov versus Deep Blue: Computer Chess Comes of Age. The review appeared in Science for 1997 June 6.
Roofs and Boxes is an example to illustrate that extrapolating past experience to predict the future usually involves recognitions of phenomena in the world and not just the sequence of inputs. The problem is too hard for now.
Philosophical and scientific presuppositions of logical AI appeared in Logical Foundations for Cognitive Agents: Contributions in Honor of Ray Reiter, edited by H. J. Levesque and F. Pirri, Springer-Verlag, 1999.
Parameterizing the Set of Models of a Propositional Theory
It is often inadequate that a theory be consistent, i.e. have models. It should have enough models. We discuss parameterizing the set of models in the special case of propositional satisfiability.
Appearance and Reality: A challenge to machine learning contains a puzzle whose solution is to determine the reality behind the appearance you see on the page. The challenge is to make machine learning programs and scientific discovery programs that can find the reality behind appearance in this simple case.
Modality, si! Modal logic, no! argues that there are better ways, especially for AI, of treating modalities than any kind of modal logic. It appeared in Studia Logica, volume 59, 1997John Searle's chinese room argument contains a refutation of that argument that computers can't be conscious.
The Common Business Communication Language, published in 1982, proposes a language for inter-business inter-computer commmunication. Most of the ideas in this paper have been re-invented in connection with electronic commerce, specifically in connection with XML.
Criteria for usefulness of computers in offices is a 1982 article. Its observations are mainly confirmed, but some of the measures it advocates are still not implemented.
Networks considered harmful - for electronic mail is a 1989 editorial in CACM. Now that Internet is universally available, its considerations are mostly obsolete.
THE HOME INFORMATION TERMINAL---A 1970 VIEW This article was published in Man and Computer. Proc. int. Conf., Bordeaux 1970, pp. 48-57 (Karger, Basel 1972). It is interesting to compare its 1970 proposals with the current situation, 30 years later. I have decorated it with footnotes commenting on the 1970 situation and making comparisons. Some of the improvements advocated in the paper are still yet to come. I claim quite a few prophet points for the article.
2006 January: I seem to have forgotten to put links to my mathematical articles on this web page - even the ones I have in computer form. Maybe I'll get around to it.
AN EVERYWHERE CONTINUOUS NOWHERE DIFFERENTIABLE FUNCTION This note was published in the AMERICAN MATHEMATICAL MONTHLY in 1953 December. The point of the example is that the proof is 13 lines of rather easy mathematics.The date given is when the paper was last revised. Actually, all papers are in progress, since I sometimes improve published papers when I think of something new. Most will not be submitted for formal publication, but they may be referenced.
The article will surely be changed before being submitted to a conference or a journal. Comments are welcomed.
The 1996 The Well-Designed Child discusses the initial knowledge of the world that makes a baby more competent than a "Lockean baby" would be. Slides from a 2007 Sept 27 lecture in Rome have been added. I hope the new material is an improvement.
Partial Formalizations and the Lemmings Game 1994 Nov
Situation Calculus with Concurrent Events and Narrative - 1994 This article was intended to be superseded by Combining Narratives by McCarthy and Costello. However, I have become attached to some of the constructions of the original article that were omitted from the new version.
Concepts of Logical AI has a paragraph each about each of approximately 50 concepts.
From Here to Human-level AI, 1996 August, was the basis of an invited talk at KR-96 in 1996 November.Phenomenal Data Mining concerns finding relations between data and phenomena and not just relations within the data. There isn't much AI in the paper - yet, but the idea for phenomenal data mining has somewhat of a philosophical and AI origin.
Phenomenal Data Mining is a slightly updated version of the above that will appear in SIGKDD Explorations. A further edited version will appear in CACM.
Elaboration Tolerance discusses making logical representations of facts that can accept various kinds of modifications easily - best by the addition of sentences. - 1997 Sept 9, updated 1997 Dec 14
FORMALIZATION OF STRIPS IN SITUATION CALCULUS is a 1985 note aimed at regarding STRIPS as a proof strategy for an interactive theorem prover using a situation calculus formalism. It doesn't quite get there.
NOTES ON SELF-AWARENESS is a preliminary report related to the 2004 April DARPA Workshop on self-awareness.
AI needs a basic research document
ADVOCACY contains references to pages advocating something or other.
ESSAYS contains essays about various topics written from time to time. Some of them are supposed to be funny.
Here are some references to home pages of individuals and institutions concerned with AI. I'd be glad to have more references.
Here is a Emacs Lisp file of mathematical, physical and astronomical facts that I prepared for my own use which I am making available by request. I have called it facts.txt, so that Netscape and competitors will treat it right. Xemacs and FSF Emacs would prefer it renamed to facts.el; then they will treat it right. The emacs lisps are subsets of Common Lisp, so it can be loaded into Common Lisp and used there.
Here's a puzzle expressing my attitude towards many human problems. Look at THE DOCTOR'S DILEMMA
This page has the permanent URL: http://purl.oclc.org/NET/jmc/ . The theory is that if http://www-formal.stanford.edu/jmc has to be changed (which is not planned) then OCLC will redirect the reference to the new URL, assuming I have provided one.
On 1999 February 15 I was interviewed by Dorian Devins for a radio program called the Green Room. The interview was broadcast live, and if you want to hear it, you can go to the Green Room site and look for Feb 15, 1999.
A commentary on important events of the 20th century and expected events of the next was solicited by the San Jose Mercury and published on 1999 June 24. The above is a slightly expanded version.
Universality: or why there are separate sciences tells why a universal mechanism at one level of organization makes the details of lower levels irrelevant. Thus universal computers make computer science independent of basic physics.
Some of my old files that I think have current interest are linked from oldnotes.html. I start on 2004 June 4 with one file on keyboards for arbitrary character sets.
..... 