Next: What Kinds of Facts Up: Towards a Mathematical Science Previous: Introduction

# What Are The Entities With Which Computer Science Deals?

These are problems, procedures, data spaces, programs representing procedures in particular programming languages, and computers.

Problems and procedures are often confused. A problem is defined by the criterion which determines whether a proposed solution is accepted. One can understand a problem completely without having any method of solution.

Procedures are usually built up from elementary procedures. What these elementary procedures may be, and how more complex procedures are constructed from them, is one of the first topics in computer science. This subject is not hard to understand since there is a precise notion of a computable function to guide us, and computability relative to a given collection of initial functions is easy to define.

Procedures operate on members of certain data spaces and produce members of other data spaces, using in general still other data spaces as intermediates. A number of operations are known for constructing new data spaces from simpler ones, but there is as yet no general theory of representable data spaces comparable to the theory of computable functions. Some results are given in [McC63].

Programs are symbolic expressions representing procedures. The same procedure may be represented by different programs in different programming languages. We shall discuss the problem of defining a programming language semantically by stating what procedures the programs represent. As for the syntax of programming languages, the rules which allow us to determine whether an expression belongs to the language have been formalized, but the parts of the syntax which relate closely to the semantics have not been so well studied. The problem of translating procedures from one programming language to another has been much studied, and we shall try to give a definition of the correctness of the translation.

Computers are finite automata. From our point of view, a computer is defined by the effect of executing a program with given input on the state of its memory and on its outputs. Computer science must study the various ways elements of data spaces are represented in the memory of the computer and how procedures are represented by computer programs. From this point of view, most of the current work on automata theory is beside the point.

Next: What Kinds of Facts Up: Towards a Mathematical Science Previous: Introduction

John McCarthy
Tue May 14 13:32:03 PDT 1996