Theoretical computer science began by proving what can never be proved
Some of the deepest results about computing concern what cannot be done. In 1931 Kurt Gödel showed with his incompleteness theorem that some statements can be neither proved nor disproved. That result helped launch a field that studies computation through pure mathematics, asking what machines can do in principle rather than how to build them.
Theoretical computer science sits where computing meets mathematics and logic, and during the 20th century it broke away to become a discipline in its own right. Its pioneers included Alonzo Church, Alan Turing, Stephen Kleene, John von Neumann and Noam Chomsky, alongside Gödel and Claude Shannon. What sets the work apart is its insistence on mathematical rigour.
Milestones arrived steadily. Shannon's 1948 theory of communication founded information theory. In the same decade, Donald Hebb proposed a mathematical model of how brains learn, an idea that, as biological evidence mounted, gave rise to neural networks and parallel distributed processing. In 1971 Stephen Cook, and independently Leonid Levin, showed that practically important problems can be NP-complete, a turning point for the study of computational difficulty.
The territory is wide and hard to fence in. The main professional group for algorithms and computation theory lists topics from data structures and cryptography to quantum computing, machine learning, computational biology and game theory. At the centre sits the algorithm: a finite list of precise instructions that moves step by step from an input to an output and then stops. Some algorithms deliberately use random input. Automata theory studies idealised self-running machines, its name taken from a Greek word meaning self-acting. Coding theory designs codes for compressing data, correcting errors and keeping messages secret.
Complexity theory tries to sort problems by how inherently hard they are. A problem counts as difficult if solving it demands heavy resources whatever method is used, measured in time and memory, but also in communication, circuit size or the number of processors. One of its jobs is to mark out the practical limits of what computers can and cannot achieve.
Source: Theoretical computer science
