Theoretical computer science begins with a question audacious enough to stand beside any in physics: what can be computed at all? In 1936, before a single electronic computer existed, Alan Turing answered it with a thought experiment, an imaginary machine of tape and symbols, and in answering it drew the boundary of the possible for every computer that would ever be built. That is the strange power of this subject. Its deepest results concern no particular machine, no silicon and no software, but the nature of procedure itself, and they are won the way theorems are won, by pure thought. A student who takes it up is not learning to use computers. They are learning what computation is, and what it can never be.
Some of its treasures can be held in the hand. Turing's own argument shows that no program can ever be written that decides, for every program, whether it will finish or run forever: a permanent boundary stone, laid down by a proof a determined student can master in an afternoon. The question of whether a number is prime, as old as Euclid, was shown to be decidable quickly only in 2002, by Manindra Agrawal, Neeraj Kayal and Nitin Saxena at IIT Kanpur, with mathematics that asks nothing more than a good command of algebra and the nerve to use it. And over the whole field stands a single open question, the way quantum gravity stands over physics: whether every problem whose answer can be checked quickly can also be solved quickly. On that question, P versus NP, rests the security of every cipher in use today, and a million-dollar prize sits unclaimed beside it, which is the smallest of the reasons to try.
Alongside computation stands information. In a single paper in 1948, Claude Shannon showed that messages, codes and noise obey exact mathematical laws, and gave the world the bit, the unit in which this page, every genome, and every signal from a distant spacecraft is now measured. The bridge to physics runs in both directions: entropy crossed over from steam engines into the theory of information, and information has since crossed back, into the thermodynamics of black holes and into quantum computation, where the strangeness of the quantum world becomes a genuinely new kind of computational power. A theory of computation is, in the end, a theory of what any system, a machine, a market, or a mind, can do in bounded time, and that is why its reach keeps outrunning its name.
Beneath it all, as everywhere, lies mathematics. Logic gives the subject its skeleton, and Gödel's incompleteness stands behind Turing's undecidability like a mountain behind its foothill. Combinatorics and graph theory carry the analysis of algorithms; probability powers the randomised methods on which modern computing leans; algebra and number theory hold up cryptography and the codes that correct errors in every transmission; and algebraic geometry now reaches into the complexity of computation itself. Questions of this kind are alive in our own community, where the classical problem of counting points on curves and surfaces over finite fields meets the modern demand that the counting be done in polynomial time.
And as with every subject at FARII, students go to the sources. Turing's paper of 1936, Shannon's of 1948, Gödel's of 1931: the founding documents of this field are young enough to be read in their authors' own voices and deep enough that they have not been exhausted yet. A student who meets them there learns the lesson the subject itself keeps teaching, that the simplest questions, asked stubbornly enough, open onto the largest worlds, and that a mind which has learned to reason about all possible procedures has learned something about thought itself.