Computation Theory
What can be computed? Turing machines, decidability, computational complexity — the mathematical foundations of what computers can and cannot do.
Computation theory asks the most fundamental question in computer science: what problems can be solved by an algorithm? Alan Turing (1936) and Alonzo Church independently showed that a surprisingly simple abstract machine — the Turing machine — can compute anything that is computable. This Church-Turing thesis remains unrefuted. But Turing also proved that some problems are undecidable: no algorithm can solve the halting problem (determining whether an arbitrary program terminates). This connects directly to Godel's incompleteness — both reveal fundamental limits of formal systems. Computational complexity theory then asks: among computable problems, which are tractable? The P vs NP question — whether problems whose solutions can be verified quickly can also be solved quickly — is one of the deepest open problems in mathematics, with a million-dollar prize. These results shape everything from cryptography (which relies on hard problems) to AI (which seeks efficient approximations to intractable problems).