March 1970 - Vol. 13 No. 3

March 1970 issue cover image

Features

Research and Advances

A program to teach programming

The TEACH system was developed at MIT to ease the cost and improve the results of elementary instruction in programming. To the student, TEACH offers loosely guided experience with a conversational language which was designed with teaching in mind. Faculty involvement is minimal. A term of experience with TEACH is discussed. Pedagogically, the system appears to be successful; straighforward reimplementation will make it economically successful as well. Similar programs of profound tutorial skill will appear only as the results of extended research. The outlines of this research are beginning to become clear.
Research and Advances

Experiments with the M & N tree-searching program

The M & N procedure is an improvement to the mini-max backing-up procedure widely used in computer programs for game-playing and other purposes. It is based on the principle that it is desirable to have many options when making decisions in the face of uncertainty. The mini-max procedure assigns to a MAX (MIN) node the value of the highest (lowest) valued successor to that node. The M & N procedure assigns to a MAX (MIN) node some function of the M (N) highest (lowest) valued successors. An M & N procedure was written in LISP to play the game of kalah, and it was demonstrated that the M & N procedure is significantly superior to the mini-max procedure. The statistical significance of important conclusions is given. Since information on statistical significance has often been lacking in papers on computer experiments in the artificial intelligence field, these experiments can perhaps serve as a model for future work.
Research and Advances

Measurements of segment size

Distributions of segment sizes measured under routine operating conditions on a computer system which utilizes variable sized segments (the Burroughs B5500) are discussed. The most striking feature of the measurements is the large number of small segments—about 60 percent of the segments in use contain less than 40 words. Although the results are certainly not installation independent, and although they are particularly influenced by features of the B5500 ALGOL system, they should be relevant to the design of new computer systems, especially with respect to the organization of paging schemes.
Research and Advances

On an algorithm for nonlinear minimax approximation

Certain nonlinear minimax approximation problems are characterized by properties which permit the application of special algorithms, mainly based on the exchange algorithms of Remes (1934, 1935), for their solution. In this paper the application to problems of this type of a general nonlinear algorithm due to Osborne and Watson (1969) is considered. Examples are given to illustrate that this algorithm can give satisfactory results and, in particular, can successfully solve problems which lead to difficulties with the more conventional specialist method.
Research and Advances

A comparison of error improvement estimates for adaptive trapezoid integration

Various simple choices of error improvement estimates for the trapezoid rule are studied to demonstrate a comparison procedure which is relatively independent of the profusion of adaptive search and stopping strategies. Comparisons are based on xr, 0 ≤ r, 0 ≤ x ≤ 1; the inclusion of the non-integer powers makes this more realistic than the usual polynomial based comparison. Behavior near the singularity was found to be the dominant factor, and a new estimate, based on a constant curvature assumption and parametric differences, was considered slightly better than the other choices considered.
Research and Advances

A deductive question-answerer for natural language inference

The question-answering aspects of the Protosynthex III prototype language processing system are described and exemplified in detail. The system is written in LISP 1.5 and operates on the Q-32 time-sharing system. The system's data structures and their semantic organization, the deductive question-answering formalism of relational properties and complex-relation-forming operators, and the question-answering procedures which employ these features in their operation are all described and illustrated. Examples of the system's performance and of the limitations of its question-answering capability are presented and discussed. It is shown that the use of semantic information in deductive question answering greatly facilitates the process, and that a top-down procedure which works from question to answer enables effective use to be made of this information. It is concluded that the development of Protosynthex III into a practically useful system to work with large data bases is possible but will require changes in both the data structures and the algorithms used for question answering.
Research and Advances

PDEL—a language for partial differential equations

Conventional computer methods available to solve continuous system problems characterized by partial differential equations are very time-consuming and cumbersome. A convenient, easy to learn and to use, high level problem oriented language to solve and study partial differential equation problems has been designed; a practical translator for the language has also been designed, and a working version of it has been constructed for a significant portion of the language. This Partial Differential Equation Language, PDEL, is outlined, and the highlights of the translator are briefly summarized.
Research and Advances

A number system for the permutations

A number system described here is particularly suitable for numbering the permutations. An algorithm is then presented by which the permutation associated with a number of this kind may be obtained. Since arithmetical operations, such as the addition of 1, are easily performed in the number system, one may make use of the algorithm to generate the permutations one at a time, using a minimal amount of work space. Employed for this purpose, it provides an alternative to the method given in [1].

Recent Issues

  1. November 2024 CACM cover
    November 2024 Vol. 67 No. 11
  2. October 2024 CACM cover
    October 2024 Vol. 67 No. 10
  3. September 2024 CACM cover
    September 2024 Vol. 67 No. 9
  4. August 2024 CACM cover
    August 2024 Vol. 67 No. 8