Foundations of Computer Science

We’ll start our journey by looking at the foundations of Computer Science. The fundamental question of Computer Science is something akin to “What kinds of problems can be solved with algorithms.” It was first asked formally by David Hilbert in 1901 and first answered by Alan Turing in 1936. This is the central question of computability theory, that establishes the foundational theory for what can be done with any computer.

We will examine this question first, in 1  What is Computation?. There we will encounter the concept of a Turing machine, an abstract computer model that we define to study the properties of computation and computable problems irrespective of any concrete machine our current technology supports. Turing machines let us answer which kinds of problems are, in principle, undecidable —which means that no algorithm can ever be devised to solve them completely. Surprisingly, there are many of those, not all esoteric; there are very practical problems in Computer Science that we know are mathematically impossible to solve.

Turing machines also give a precise definition of algorithm, and we will tackle this notion next, in 2  Algorithms, Lots of Algorithms. We will see how algorithms can be used to systemathize the solution to computational problems, and we will learn the characteristics of good algorithms. We will also see some core ideas that help computer scientists design and analyze algorithms, such as recursion, divide-and-conquer, and dynamic programming.

The next ingredient in the foundational theory of Computer Science is the surprising relationship between languages and machines. Formal language theoryallows us to formalize the notion of a language, whether it is a human language like English or Spanish, a programming language like Python or C#, and any technical, abstract, or mathematical notations used in many fields. We will look at the intriguing world of computational languages in 3  Languages and Computation.

Finally, once we lay out the limits of computation, we can ask which computable problems are easier or harder. Complexity theory deals with the complexity of different problems, and we will meet it in 4  Easy and Hard Problems. It asks how efficiently, most commonly in terms of computing time and memory, we can solve any problem. For some problems, we can even prove that we have found the most efficient algorithm anyone could ever develop. The most important problem in complexity theory, and probably in Theoretical Computer Science, is the famous question of P vs NP, which is ultimately a question about the nature of really hard problems.