A short program which redefines parts of the LISP 1.5 compiler and

suppresses compiler print out (at user's option) is described.

Interesting work is being done in programming computers to solve

problems which require a high degree of intelligence in humans.

However, certain elementary verbal reaesoning processes so simple

they can be carried out by any non-feeble-minded human have yet to be

simulated by machine programs.

This paper will discuss programs to manipulate in a suitable formal

language (most likely a part of the predicate calculus) common

instrumental statements. The basic program will draw immediate

conclusions from a list of premises. These conclusions will be

either declarative or imperative sentences. When an imperative

sentence is deduced the program takes a corresponding action. These

actions may include printing sentences, moving sentences on lists,

and reinitiating the basic deduction process on these lists.

Facilities will be provided for communication with humans in the

system via manual intervention and display devices connected to the

computer.

Storage conventions and a basic set of functions for LISP 2 are

proposed. Since the memo was written, a way of supplementing the

features of this system with the unique storage of list structure

using a hash rule for computing the address in a separate free

storage area for lists has been found.

An example of a typical Advice-Taker axiomatization of a situation is given, and the situation is programmed in LISP as an indication

of how the Advice-Taker could be expected to react. The situation

chosen is the play of a hand of bridge.

An exposition of the MacMahon Squares problem together with some 'theoretical' results on the nature of its solutions and a short discussion of an ALGOL program which finds all solutions are

contained herein.

Program execution time can be reduced, by a considerable amount, by optimizing the 'For-loops' of Algol programs. By judicious use of index registers and by evaluating all the sub-expressions whose

values are not altered within the 'For-loop', such optimization can be achieved.

In this project we develop an algorithm to optimize Algol programs in list-structure form and generate a new source language program, which contains the 'desired contents in the index registers' as a

part of the For-clause of the For-statement and additional statements for evaluating the same expressions outside the 'For-loop' This optimization is performed only for the innermost 'For-loops'.

The program is written entirely in LISP. Arrays may have any number of subscripts. Further array declarations may have variable dimensions. (Dynamic allocation of storage.) The program does not

try to optimize arithmetic expressions. (This has already been extensively investigated.)

A program that checks proofs in J. A. Robinson's formulation of

predicate calculus has been programmed in LISP 1.5. The program is

available in CTSS at Project MAC and is also available as a card

deck. The program is used for class exercises at Stanford.

This paper is a discussion of several methods for the connection of

a television camera to the PDP-1 computer. Three of these methds

are discussed in detail and have in common that only a 36 bit

portion of any horizontal scanning line may be read and this

information is read directly into the working registers of the

computer. The fourth involves a data channel to read information

directly into the core memory of the computer, and is mentioned only

in passing. The major concepts and some of the details of these

methods are due to Marvin Minsky.

The following is an excerpt from a proposal to ARPA and gives some

of the project plans for the near future.

The purpose of this paper is to identify and discuss a number of

theoretical problems whose solutions seem feasible and likely to

advance the practical art of computation. The problems that will be

discussed include the following:

1. Semantics of programming languages. What do the strings of

symbols representing computer programs, statements, declarations,

labels, etc., denote? How can the semantics of programming

languages be described formally?

2. Data spaces. What are the spaces of data on which computer

programs act and how are they built up up from simpler spaces?

3. How can time dependent and simultaneous processes be described?

4. Speed of computation. What can be said about how much

computation is required to carry out certain processes?

5. Storage of information. How can information be stored so that

items identical or similar to a given item can be retrieved?

6. Syntax directed computation. What is the appropriate domain for

computations described by productions or other data format

recognizers?

7. What are the appropriate formalisms for writing

proofs that computer programs are equivalent?

8. In the view of Godel's theorem that tells us that any formal

theory of computation must be incomplete, what is a reasonable

formal system that will enable us to prove that programs terminate

in practical cases?

SIMPLE SIMON is a program which solves the problem of finding an

object satisfying a predicate from a list of facts. It operates by

backward chaining. The rules of procedure and heuristics are

discussed and the structure of the program is outlined.

A discussion of the programming and hardware characteristics of the

analog to digital converter on the PDP-1 is given; several sample

programs are also presented.

Using the formalism of the Newell-Shaw-Simon General Problem Solver

to solve problems expressed in McCarthy's Advice Taker formalism is

discussed. Some revisions of the formalism of and

described in AI Memo 2 are proposed.

A description of the programming required to utilize the TV camera

connected to the PDP-1 and of the initial collection of programs.

A program is described which traces around objects in a picture,

using the picture scanner attached to the PDP-1 computer, and fits

curves to the edges.

Some comments are made on the characteristics believed desirable in

the next eye for the Stanford Artificial Intelligence Project and a

proposal is given for a program to input scenes using the eye.

A formal theory is described which incorporates the 'assignment'

function a(i, k, psi) and the 'contents' function c(i, psi). The

axioms of the theory are shown to comprise a complete and consistent

set.

The Heuristic Dendral program for generating explanatory hypotheses

in organic chemistry is described as an application of the

programming language LISP. The description emphasizes the

non-chemical aspects of the program, particularly the 'topologist'

which generates all tree graphs of a collection of nodes.

Heuristic DENDRAL is a computer program written to solve problems of

inductive inference in organic chemistry. This paper will use the

design of Heuristic DENDRAL and its performance on different problems

for a discussion of the following topics:

l. the design for generality;

2. the performance problems attendent upon too

much generality

3. the coupling of expertise to the general problem solving

processes,

4. the symbiotic relationship between generality and

expertnness of problem solving systems.

We conclude the paper with a view of the design for a general problem

solver that is a variant of the "big switch" theory of generality.

An elementary outline of the theorem-proving approach to automatic

program synthesis is given, without dwelling on technical details.

The method is illustrated by the automatic construction of both

recursive and iterative programs operating on natural numbers, lists,

and trees.

In order to construct a program satisfying certain specifications, a

theorem induced by those specifications is proved, and the desired

program is extracted from the proof. The same technique is applied

to transform recursively defined functions into iterative programs,

frequently with a major gain in efficiency.

It is emphasized that in order to construct a program with loops or

with recursion, the principle of mathematical induction must be

applied. The relation between the version of the induction rule used

and the form of the program constructed is explored in some detail.

A simulation relation between programs is defined which is

quasi-ordering. Mutual simulation is then an equivalence relation,

and by dividing out by it we abstract from a program such details as

how the sequencing is controlled and how data is represented. The

equivalence classes are approximations to the algorithms which are

realized, or expressed, by their member programs.

A technique is given and illustrated for proving simulation and

equivalence of programs; there is an analogy with Floyd's technique

for proving correctness of programs. Finally, necessary and

sufficient conditions for simulation are given.

Procedures are described for discovering the intention of a speaker

by relating the Conceptual Dependence representation of the speaker's

utterance to the computer's world model such that simple implications

can be made. These procedures function at levels higher than that of

structure of the memory. Computer understanding of natural language

is shown to consist of the following parts: assigning a conceptual

representation to an input; relating that representation to the

memory such as to extract the intention of the speaker; and selecting

the correct response type triggered by such an utterance according to

the situation.

I argue that the present situation in formal linguistics, where much

new work is presented as being a "model of the brain", or of "human

language behavior", is an undesirable one. My reason for this

judgement is not the conservative (Braithwaitian) one that the

entities in question are not really models but theories. It is

rather that they are called models because they cannot be theories of

the brain at the present stage of brain research, and hence that the

use of "model" in this context is not so much aspirational as

resigned about our total ignorance of how the brain stores and

processes linguistic information. The reason such explanatory

entities cannot be theories is that this ignorance precludes any

"semantic ascent" up the theory; i.e., interpreting the items of the

theory in terms of observables. And the brain items, whatever they

may be, are not, as Chomsky has sometimes claimed, in the same

position as the "occult entities" of Physics like Gravitation; for

the brain items are not theoretically unreachable, merely unreached.

I then examine two possible alternate views of what linguistic

theories should be proffered as theories of: theories of sets of

sentences, and theories of a particular class of algorithms. I argue

for a form of the latter view, and that its acceptance would also

have the effect of making Computational Linguistics a central part of

Linguistics, rather than the poor relation it is now.

I examine a distinction among "linguistic models" proposed recently

by Mey. who was also arguing for the self-sufficiency of

Computational Linguistics, though as a "theory of performance". I

argue that his distinction is a bad one, partly for the reasons

developed above and partly because he attempts to tie it to Chomsky's

inscrutable competance-performance distinction. I conclude that the

independence and self-sufficiency of Computational Linguistics are

better supported by the arguments of this paper.

We discuss the class of program schemas augmented with equality

tests, that is, tests of equality between terms. In the first part

of the paper we illustrate the "power" of equality tests. It turns

out that the class of program schemas with equality is more powerful

than the "maximal" classes of schemas suggested by other

investigators. In the second part of the paper, we discuss the

decision problems of program schemas with equality. It is shown, for

example, that while the decision problems normally considered for

schemas (such as halting, divergence, equivalence, isomorphism and

freedom) are decidable for ianov schemas. They all become

undecidable if general equality tests are added. We suggest,

however, limited equality tests which can be added to certain

subclasses of program schemas while preserving their decidability

property.

The Heurisic DENDRAL program uses an information processing model of

scientific reasoning to explain experimental data in organic

chemistry. This report summarizes the organization and results of the

program for computer scientists. The program is divided into three

main parts: planning, structure generation, and evaluation.

The planning phase infers constraints on the search space from the

empirical data input to the system. The structure generation phase

searches a tree whose termini are models of chemical models using

pruning heuristics of various kinds. The evaluation phase tests the

candidate structures against the original data. Results of the

program's analyses of some tests are discussed.

The treatment of a certain class of adverbs in conceptual

representation is given. Certain adverbs are shown to be

representative of complex belief structures. These adverbs serve as

pointers that explain where the sentence that they modify belongs in

a belief structure.

The paper describes a system of semantic analysis and generation,

programmed in LISP 1.5 and designed to pass from paragraph length

input in English to French via an interlingual representation. A

wide class of English input forms will be covered, but the vocabulary

will initially be restricted to one of a few hundred words. With

this subset working, and during the current year (1971-72), it is

also hoped to map the interlingual representation onto some predicate

calculus notation so as to make possible the answering of very simple

questions about the translated matter. The specification of the

translation system itself is complete, and its main points are:

i) It translates phrase by phrase--with facilities for reordering

phrases and establishing essential semantic connectivities between

them--by mapping complex semantic stuctures of "message" onto each

phrase. These constitute the interlingual representation to be

translated. This matching is done without the explicit use of a

conventional syntax analysis, by taking as the appropriate matched

structure the "most dense" of the alternative structures derived.

This method has been found highly successful in earlier versions of

this analysis system.

ii) The French output strings are generated without the explicit use

of a generative grammar. That is done by means of STEREOTYPES:

strings of French words, and functions evaluating to French words,

which are attached to English word senses in the dictionary and built

into the interlingual representation by the analysis routines. The

generation program thus receives an interlingual representation that

already contains both French output and implicit procedures for

assembling the output, since the stereotypea are in effect recursive

procedures specifying the content and production of the output word

strings. Thus the generation program at no:time consults a word

dictionsary or inventory of grammar rules.

It is claimed that the system of notation and translation described

is a convenient one for expressing and handling the items of semantic

information that are ESSENTIAL to any effective MT system. I discuss

in some detail the semantic information needed to ensure the correct

choice of output prepositions in French; a vital matter inadequately

treated by virtually all previous formalisms and projects.

The revival of interest in Automatic Programming is considered. The

research is divided into direct efforts and theoretical developments

and the successes and prospects of each are described.

Expert judges, psychiatrists and computer scientists, could not

correctly distinguish a simulation model of paranoid processes from

actual paranoid patients

We consider the class of linear recursive programs. A linear

recursive program is a set of procedures where each procedure can

make at most one recursive call. The conventional stack

implementation of recursion requires time and space both proportional

to n, the depth of recursion. It is shown that in order to

implement linear recursion so as to execute in time n one doesn't

need space proportional to n: n**ε for sufficiently small ε will do.

It is also known that with constant space one can implement linear

recursion in time n**2. We show that one can do much better:

n**(1+ε) for arbitrarily small ε. We also describe an algorithm that

lies between these two: it takes time n*log n and space log n.

It is shown that several problems are closely related to the linear

recursion problem, for example, the problem of reversing an input

tape given a finite automaton with several one-way heads. By casting

all these problems into canonical form, efficient solutions are

obtained simultaneously for all.

This paper is primarily a user's manual for LCF, a proof-checking

program for a logic of computable functions proposed by Dana Scott in

1969, but unpublised by him. We use the name LCF also for the logic

itself, which is presented at the start of the paper. The

proof-checking program is designed to allow the user interactively to

generate formal proofs about computable functions and functionals

over a variety of domains, including those of interest to the

computer scientist--for example, integers, lists and computer

programs and their semantics. The user's task is alleviated bu two

features: a subgoaling facility and a powerful simplification

mechanism. Applications include proofs of program correctness and in

particular of compiler correctness; these applications are not

discussed herein, but are illustrated in the papers referenced in the

introduction.