Topic: The mathematical foundations of computer science.
We explore the fundamental limits of what machines can actually do. We move beyond simple programming to classify problems into those that are decidable and those for which no algorithm could ever exist. By studying the Halting Problem, we discover that there are definitive "blind spots" in the landscape of computation, proving that some questions are inherently unanswerable for any computer.
Before we can build machines, we must master the language they are built upon. This section covers the formal mathematical frameworks—sets, relations, and propositional logic—that allow us to describe computation with absolute precision. We use these tools to model the state space of algorithms and define exactly how inputs transition to outputs within a mathematical system.
Not all infinities are created equal, and understanding this is key to computer science. We compare the set of natural numbers (countable) with the set of real numbers (uncountable) to demonstrate why some computational tasks are fundamentally impossible. Through Cantor’s diagonalisation argument, we gain a rigorous understanding of the limitations of mapping data to discrete algorithmic steps.
The Turing machine is the theoretical bedrock of modern computing. We examine how this abstract machine uses a tape and a finite set of states to process information. You will learn how to simulate complex algorithms on this simple model, how to represent input/output sequences, and how to encode the configuration of a machine itself into a numerical format.
To treat "computation" as a mathematical object, we must learn to treat code as data. Gödel numbering allows us to map symbols, words, and even entire programs into unique integers. This encoding process is the "secret sauce" that allows us to prove properties about software by doing math on numbers rather than complex strings of code.
This is where we connect the dots between known problems and unknown ones. Reduction is a powerful technique where we show that if we can solve Problem A, we can automatically solve Problem B. We use this to prove that certain problems are "at least as hard" as others, ultimately using this logic to categorize complex problems as non-computable.