CMPS 260: Introduction
Adapted from Elements of the Theory of Computation, by Lewis and Papadimitriou

Every academic discipline has an underlying body of theory that serves as its foundation. This theory addresses questions/issues that are fundamental to the discipline.

Examples:

• Mathematical Logic (a sub-discipline of mathematics and philosophy) employs various precise/formal models that address the nature of reasoning. E.g., In Propositional and Predicate Logic, the Modus Ponens rule of inference says that if, with respect to boolean expressions P and Q, you know both P and P ⇒ Q to be true, then you can conclude that Q is true. As an example, let P denote the proposition "It is raining" and Q denote the proposition "The sidewalk is wet".
• Physics addresses the nature of physical matter, from the smallest subatomic particles to the entire universe. From Tennessee Tech's web page:

  Physicists try to develop conceptual and mathematical models that describe interactions between entities (both big and small) and that can be used to extend our understanding of how the universe works at different scales.

• Biology addresses the nature of life.
• Psychology addresses the nature of human/animal behavior.

What about Computer Science? What fundamental questions/issues does it address? The nature of computers? Well, maybe. But one computer scientist (most likely Edsger Dijkstra) quipped that such a name is analagous to "washing machine science", which seems ridiculous. Dijkstra also said, "Computer science is no more about computers than astronomy is about telescopes."

Dijkstra's point was that CS's fundamental concern is not the nature of computers, per se, but rather the nature of computation. Thus, perhaps a better name would be computation science or computing science.

What is computation? How to describe one? How to specify one (i.e., describe rules by which a computation is to be carried out)? Such a set of rules is referred to as an algorithm, and notations for describing algorithms are of particular interest to those who study/design programming languages.

We commonly employ computation to solve problems. (This is what software systems are intended to do.) One relevant and fundamental question is,

Are there problems that are "unsolvable" via computation, in the sense that there exists no algorithm that can be fairly said to constitute a solution to the problem?

The answer is yes! In fact, the overwhelming majority of problems are unsolvable! The area of CS that is concerned with determining which problems are solvable and which aren't is known as computability theory.
Note: To say that a computational problem is unsolvable does not mean that no algorithmic solution has yet been found; rather, it means something stronger, namely that no algorithmic solution can possibly be found, because none exists!
End of note.

Now consider only the solvable problems. It turns out that there are some whose solution is infeasible, in the sense that even a very powerful (i.e., fast) computer, running the most efficient possible program, would be forced to spend a huge amount of time and/or memory before the computation was finished. (Such problems are sometimes referred to as being intractable.) It would be useful to identify such problems so as to avoid making futile and costly attempts to develop solutions.

Even with respect to tractable problems, it is interesting to classify them according to "how difficult" they are to solve, in the sense of how many computational resources (time and space) —as a function of input size— are required to compute a solution. As an example, it is known that the general problem of sorting cannot be solved using fewer than a number of operations proportional to N⋅log(N), where N is the number of items in the collection to be sorted. The branch of computer science that addresses this issue is complexity theory.

The way that we address fundamental questions about the nature of computation in a precise, rigorous way is to devise models of computation and to explore their characteristics and capabilities.

This is what this course aims to do.