Ph.D. thesis, Stanford University.

It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be "reduced" to the problem of determining whether a given propositional formula is a tautology. Here "reduced" means, roughly speaking, that the first problem can be solved deterministically in polynomial time provided an oracle is available for solving the second. From this notion of reducible, polynomial degrees of difficulty are defined, and it is shown that the problem of determining tautologyhood has the same polynomial degree as the problem of determining whether the first of two given graphs is isomorphic to a subgraph of the second. A method of measuring the complexity of proof procedures for the predicate calculus is introduced and discussed.

The importance of effective task representations in the design of programs intended to exhibit sophisticated behaviour manifests itself in the area of Picture Interpretation as the so-called ‘Linguistic Approach’. A brief survey of Pattern Description Languages leads up to an analysis of a simple letter recognition task from which it is argued that at least two types of description of the pattern must be utilised if any significant pattern generalisation is to be achieved, and in general that all picture interpretation tasks involve descriptions in two domains. Further support for this viewpoint is provided by a characterization of the problem of interpreting line diagrams as pictures of three dimensional sceness, in which the form of these decriptions and of their interrelation by an algorithm is described in detail. The paper concludes by relating these ideas to the distinction between syntax and semantics, and the concept of denotation.

Amsterdam: North-Holland.

New York: American Elsevier.

New York: McGraw-Hill.

A recognition procedure with a range finder has been developed for the eye of the ETL-ROBOT, an intelligent robot studied at the Electrotechnical Laboratory. The range finder employs a vertical slit projector which projects a light beam on the objects. While the beam is moved in a field of view, the picture at each instant is picked up by a TV camera. The distance to each point can be obtained by means of trigonometrical calculation. The information thus obtained is utilized for the recognition procedure, where (1) each point is classified into lines, (2) each line is classified into planes, (3) 3-dimensional position of each plane is calculated, and (4) the object is recognized by the relationship between planes.

A paradigm enabling heuristic problem solving programs to exploit an analogy between a current unsolved problem and a similar but previously solved problem to simplify it s search for a solu­tion is outlined. It is developed in detail for a first-order resolution logic theorem prover. Descriptions of the paradigm, implemented LISP programs, and preliminary experimental results are presented. This is believed to be the firs t system that develops analogical information and exploits it so that a problem-solving program can speed its search.IJCAI-71, British Computer Society, London, 1971. Revised version in Artificial intelligence 2(2):147- 178, fall, 1971.

This paper echoes, from a philosophical standpoint, the claim of McCarthy and Hayes that Philosophy and Artificial Intelligence have important relations. Philosophical problems about the use of “intuition” in reasoning are related, via a concept of anlogical representation, to problems in the simulation of perception, problem-solving and the generation of useful sets of possibilities in considering how to act. The requirements for intelligent decision-making proposed by McCarthy and Hayes are criticised as too narrow, and more general requirements are suggested instead.See also: Artificial Intelligence, Volume 2, Issues 3–4, Winter 1971, Pages 209–225In IJCAI 1971: INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE.. Revised paper in Artificial Intelligence 2:209- 225

Proceedings of the IJCAI, pp 359-364, London: British Computer Society, September 1971