It is ACM's 40th year and an old debate continues. Is computer science a science? An engineering discipline? Or merely a technology, an inventor and purveyor of computing commodities? What is the intellectual substance of the discipline? Is it lasting, or will it fade within a generation? Do core curricula in computer science and engineering accurately reflect the field? How can theory and lab work be integrated in a computing curriculum?We project an image of a technology-oriented discipline whose fundamentals are in mathematics and engineering — for example, we represent algorithms as the most basic objects of concern and programming and hardware design as the primary activities. The view that “computer science equals programming” is especially strong in our curricula: the introductory course is programming, the technology is in our core courses, and the science is in our electives. This view blocks progress in reorganizing the curriculum and turns away the best students, who want a greater challenge. It denies a coherent approach to making experimental and theoretical computer science integral and harmonious parts of a curriculum.Those in the discipline know that computer science encompasses far more than programming. The emphasis on programming arises from our long-standing belief that programming languages are excellent vehicles for gaining access to the rest of the field — but this belief limits out ability to speak about the discipline in terms that reveal its full breadth and richness.The field has matured enough that it is now possible to describe its intellectual substance in a new and compelling way. In the spring of 1986, ACM President Adele Goldberg and ACM Education Board Chairman Robert Aiken appointed this task force with the enthusiastic cooperation of the IEEE Computer Society. At the same time, the Computer Society formed a task force on computing laboratories with the enthusiastic cooperation of the ACM.The charter of the task force has three components: Present a description of computer science that emphasizes fundamental questions and significant accomplishments.Propose a new teaching paradigm for computer science that conforms to traditional scientific standards and harmoniously integrates theory and experimentation.Give at least one detailed example of a three-semester introductory course sequence in computer science based on the curriculum model and the disciplinary description.We immediately extended our task to encompass computer science and computer engineering, for we came to the conclusion that in the core material there is no fundamental difference between the two fields. We use the phrase “discipline of computing” to embrace all of computer science and engineering. The rest of this paper is a summary of the recommendation.The description of the discipline is presented in a series of passes, starting from a short definition and culminating with a matrix as shown in the figure. The short definition:Computer science and engineering is the systematic study of algorithmic processes that describe and transform information: their theory, analysis, design, efficiency, implementation, and application. The fundamental question underlying all of computing is, “What can be (efficiently) automated?”The detailed description of the field fills in each of the 27 cells in the matrix with significant issues and accomplishments. (That description occupies about 16 pages of the report.)For the curriculum model, we recommend that the introductory course consist of regular lectures and a closely coordinated weekly laboratory. The lectures emphasize fundamentals; the laboratories emphasize technology and know-how. The pattern of closely coordinated lectures and labs can be repeated where appropriate in other courses. The recommended model is traditional in the physical sciences and in engineering: lectures emphasize enduring principles and concepts while laboratories emphasize the transient material and skills relating to the current technology.

One of the potentially most valuable research areas within artificial intelligence (Al), from the standpoint of military applications, involves the development of automatic planning systems. Al planners not only have the potential of autonomously solving various low-level planning problems such as those found in robotics applications, but can form the basis of expert consultation systems for higher level military planning problems including those involving command and control. An overview of a theory of automated adversarial planning is presented, which has been derived from the enhancement and expansion of AI techniques from the areas of automated planning and knowledge-based computer game playing. The adversarial planning paradigm has been successfully implemented in ARES (adversarial reasoning system), a computer program which can plan sequences of robot actions and compete in game environments, where various kinds of adversity (including intelligent adversarial counterplanners) exist.

We consider here the problem of building transfinite hierarchies of computable functions on the basis of their difficulty of computation. Previous hierarchies of functions through the constructive ordinals have had two major problems, each apparently caused by not having techniques to restrict the classes considered at limit ordinals. These problems are, first that every function occurs at some name for ω, or some other small ordinal, and second that two names for the same constructive ordinal have two different classes of functions associated with them.

In a suitably general context, the following analogue of the Blum Speed-up Theorem is proven: There are some infinite sets which are so difficult to enumerate that, given any order for enumerating the set, there is some other order, and some one method of enumerating the set in this second order which is much faster than any method of enumerating the set in the first ordering. It may be possible to interpret this result as a statement about the relative merits of “hardware” vs. “programming” speed-ups. The proof itself is one of the first nontrivial applications of priority methods to questions of computational complexity. As such, it perhaps represents an advance in bringing the results and techniques of contemporary “pure” recursion theory to bear on questions of computational complexity.

An attempt is made to show that there is much work in pure recursion theory which implicitly treats computational complexity of algorithmic devices which enumerate sets. The emphasis is on obtaining results which are independent of the particular model one uses for the enumeration technique and which can be obtained easily from known results and known proofs in pure recursion theory. First, it is shown that it is usually impossible to define operators on sets by examining the structure of the enumerating devices unless the same operator can be defined merely by examining the behavior of the devices. However, an example is given of an operator which can be defined by examining the structure but which cannot be obtained merely by examining the behavior. Next, an example is given of a set which cannot be enumerated quickly because there is no way of quickly obtaining large parts of it (perhaps with extraneous elements). By way of contrast, sets are constructed whose elements can be obtained rapidly in conjunction with the enumeration of a second set, but which themselves cannot be enumerated rapidly because there is no easy way to eliminate the members of the second set. Finally, it is shown how some of the elementary parts of the Hartmanis-Stearns theory can be obtained in a general setting.

In [2], Fischer has shown the existence of a bounded-truth-table degree of unsolvability which contains a collection of many-one degrees which has, under many-one reducibility, the order type, ω, of the positive integers. In [1; pg. 124], Dekker and Myhill give a construction which shows that the many-one degree of any simple set contains a collection of one-one degrees of simple sets which has, under one-one reducibility, the order type (ω + ω*) ·ω. A basic result of recursive function theory (due to Myhill) is that the creative sets form a many-one degree which consists of a single one-one degree (i.e. a single recursive isomorphism type). It is well known that the recursive sets form three many-one degrees. Two of these, the degrees of the empty set and of the set of all integers, consist of single one-one degrees.