Catalogue of Artificial Intelligence Techniques


Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML


Aliases: Self-reference

Keywords: Smalltalk

Categories: Computer Architecture , Inference and Reasoning , Theorem Proving , Programming Languages , Problem Solving , Knowledge Representation

Author(s): Se{\'a}n Matthews

It has been recognised by philosophers since classical times that self-reference (e.g. `this sentence is false') raises difficult issues in the philosophy of language, but only in this century has real progress on analysing the problems been made by, e.g., Russell, Tarski and Gödel. However, while self-reference can be difficult to treat, it is also clear that it offers powerful tools, and is anyway sometimes unavoidable, for example in the design of operating systems or ambitious knowledge representation and processing systems. Research in mathematical logic has concentrated on Gödel's incompleteness results, which show that that given a suitable true theory T of, e.g., arithmetic, statements (known as reflection principles) such as `T is consistent' are unprovable in T even though they are recognisably true. However given a theory T and reflection principle R , there is nothing to stop us defining a new theory T+R which must also be a true theory of arithmetic which is properly stronger than T (since it can prove every theorem of T , as well as the new addition R ). This procedure can even be iterated. A good exposition of this work, and further references, can be found in Girard. On the other hand, work in philosophical logic and theoretical AI has, for the most part, started from Tarski's `no truth definition' theorem, which says that it is is not possible to define in a true theory T a predicate true such that is theorem of T for every A . Effort has concentrated on finding special circumstances where such a true might, after all, be defineable, or finding restricted classes of formulae for which it might be defineable, and then investigating the properties of such systems. The results have often exhibited properties similar to modal logics. Bartlett provides an encyclopaedic collection of readings surveying this work. Finally, there is the more pragmatic area of `procedural' reflection, initiated by a doctoral thesis by Brian Smith. This investigates the properties of real computer systems which are able to make more or less radical modifications to their own running interpreters. The two commonest foundations for this work are versions of Lisp (allowing programs explicit access to an abstract `denotational semantics' style representation of the interpreter state) and Smalltalk (programs are able to patch the interpreter binary on the fly). Maes and Nardi provide a useful, though now aging, collection of papers on procedural reflection for programming systems and also for more general knowledge based systems.



Add Comment

No comments.