A recognition algorithm is exhibited whereby an arbitrary string over a given vocabulary can be tested for containment in a given context-free language. A special merit of this algorithm is that it is completed in a number of steps proportional to the “cube” of the number of symbols in the tested string. As a byproduct of the grammatical analysis, required by the recognition algorithm, one can obtain, by some additional processing not exceeding the “cube” factor of computational complexity, a parsing matrix—a complete summary of the grammatical structure of the sentence. It is also shown how, by means of a minor modification of the recognition algorithm, one can obtain an integer representing the ambiguity of the sentence, i.e., the number of distinct ways in which that sentence can be generated by the grammar. The recognition algorithm is then simulated on a Turing Machine.

Research on question answering by Raphael, Black, and Elliott, and our own work on Protosynthex II has shown that question-answering algorithms can be most easily written if the text source is in the form of simple, explicitly structured sets of subject-verb-nominal strings. Question-answering algorithms that have thus far been developed include word- and structure-matching operations and some few logical inference functions. All of the systems cited have in some fashion limited their input language to simple subject-verb-nominal strings, thus eliminating many problems of syntactic analysis and providing a normalized form for language data.

In J. A. Fodor and J. J. Katz, The structure of language. Englewood Cliffs, N.J.: Prentice- Hall, 137-151.

In Part I, four ostensibly different theoretical models of induction are presented, in which the problem dealt with is the extrapolation of a very long sequence of symbols—presumably containing all of the information to be used in the induction. Almost all, if not all problems in induction can be put in this form. Some strong heuristic arguments have been obtained for the equivalence of the last three models. One of these models is equivalent to a Bayes formulation, in which a priori probabilities are assigned to sequences of symbols on the basis of the lengths of inputs to a universal Turing machine that are required to produce the sequence of interest as output. Though it seems likely, it is not certain whether the first of the four models is equivalent to the other three.

E.A. Feigenbaum and J. Feldman (Eds.). Computers and Thought. McGraw-Hill, 1963. This collection includes twenty classic papers by such pioneers as A. M. Turing and Marvin Minsky who were behind the pivotal advances in artificially simulating human thought processes with computers. All Parts are available as downloadable pdf files; most individual chapters are also available separately. COMPUTING MACHINERY AND INTELLIGENCE. A. M. Turing. CHESS-PLAYING PROGRAMS AND THE PROBLEM OF COMPLEXITY. Allen Newell, J.C. Shaw and H.A. Simon. SOME STUDIES IN MACHINE LEARNING USING THE GAME OF CHECKERS. A. L. Samuel. EMPIRICAL EXPLORATIONS WITH THE LOGIC THEORY MACHINE: A CASE STUDY IN HEURISTICS. Allen Newell J.C. Shaw and H.A. Simon. REALIZATION OF A GEOMETRY-THEOREM PROVING MACHINE. H. Gelernter. EMPIRICAL EXPLORATIONS OF THE GEOMETRY-THEOREM PROVING MACHINE. H. Gelernter, J.R. Hansen, and D. W. Loveland. SUMMARY OF A HEURISTIC LINE BALANCING PROCEDURE. Fred M. Tonge. A HEURISTIC PROGRAM THAT SOLVES SYMBOLIC INTEGRATION PROBLEMS IN FRESHMAN CALCULUS. James R. Slagle. BASEBALL: AN AUTOMATIC QUESTION ANSWERER. Green, Bert F. Jr., Alice K. Wolf, Carol Chomsky, and Kenneth Laughery. INFERENTIAL MEMORY AS THE BASIS OF MACHINES WHICH UNDERSTAND NATURAL LANGUAGE. Robert K. Lindsay. PATTERN RECOGNITION BY MACHINE. Oliver G. Selfridge and Ulric Neisser. A PATTERN-RECOGNITION PROGRAM THAT GENERATES, EVALUATES, AND ADJUSTS ITS OWN OPERATORS. Leonard Uhr and Charles Vossler. GPS, A PROGRAM THAT SIMULATES HUMAN THOUGHT. Allen Newell and H.A. Simon. THE SIMULATION OF VERBAL LEARNING BEHAVIOR. Edward A. Feigenbaum. PROGRAMMING A MODEL OF HUMAN CONCEPT FORMULATION. Earl B. Hunt and Carl I. Hovland. SIMULATION OF BEHAVIOR IN THE BINARY CHOICE EXPERIMENT Julian Feldman. A MODEL OF THE TRUST INVESTMENT PROCESS. Geoffrey P. E. Clarkson. A COMPUTER MODEL OF ELEMENTARY SOCIAL BEHAVIOR. John T. Gullahorn and Jeanne E. Gullahorn. TOWARD INTELLIGENT MACHINES. Paul Armer. STEPS TOWARD ARTIFICIAL INTELLIGENCE. Marvin Minsky. A SELECTED DESCRIPTOR-INDEXED BIBLIOGRAPHY TO THE LITERATURE ON ARTIFICIAL INTELLIGENCE. Marvin Minsky.

In A. C. Hoggatt and F. E. Balderston (Eds.), Symposium on simulation models: Methodology and applications to the behavioral sciences. Cincinnati: South-Western Publishing, 111-138.

A statement in a spoken language may be regarded as a one-dimensional string of symbols used to communicate an idea from the speaker to a listener. The dimensionality of the statement is limited by the need for presenting words in a single time sequence. However, evidence indicates that most information and ideas are not stored by people in one-dimensional arrays isomorphic to these linear strings. This implies that a speaker must use certain complex information manipulating processes to transform the stored information to a linear output string, and that a listener, in order to "understand" the speaker, must use another set of processes to decode this linear string. In order for communication to take place, the information map of both the listener and the speaker must be approximately the same, at least for the universe of discourse.

Article based on Ph.D. dissertation at Carnegie Tech. "... the problem of meaning is of major importance in the study of the nature of intelligence, and that a useful definition of meaning must include not only denotation but connotation and implication as well. To handle these important questions it is necessary to study cognitive organizations which are more complex than those upon which most psychological theories are based. A central question is the storage of large numbers of interrelated propositions in a manner which efficiently uses memory capacity." In E.A. Feigenbaum & J. Feldman (Eds.) Computers and Thought, pp. 217-233. McGraw-Hill, 1963.

Men typically communicate with computers in a variety of artificial,stylized, unambiguous languages that are better adapted to the machinethan to the man. For convenience and speed, many future computercenteredsystems will require men to communicate with computers innatural language. The business executive, the military commander, and thescientist need to ask questions of the computer in ordinary English, andto have the computer answer the questions directly. Baseball is a first steptoward this goal.Proc. Western Joint Computer Conference 19:555-570.

The Journal of Symbolic Logic (JSL) was founded in 1936 and it has become the leading research journal in the field. Volume 71, being published during 2006, will consist of approximately 1300 pages. The Journal is distributed with The Bulletin of Symbolic Logic. The Journal and The Bulletin are the official organs of the Association for Symbolic Logic, an international organization for supporting research in symbolic logic and furthering the exchange of ideas among mathematicians, philosophers, computer scientists, linguists, and others interested in this field. The main purpose of The Journal is to publish original scholarly work in symbolic logic.