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.

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.