A
AiTechWorlds
AiTechWorlds
In 1936, a 24-year-old Cambridge mathematics student named Alan Turing was wrestling with a problem that had nothing to do with machines. He was trying to answer a pure mathematical question posed by David Hilbert: Is there a general algorithm that can determine whether any mathematical statement is true or false?
His answer was no — and the way he proved it invented the concept of computation itself.
Turing imagined an abstract device: an infinitely long tape divided into cells, a read/write head that could move left or right, and a finite set of rules governing its behavior. This thought experiment — now called the Turing Machine — became the mathematical definition of what it means to compute. Not a physical machine, but an idea precise enough to reason about the limits of all possible machines.
That same year, working independently on the other side of the Atlantic, the logician Alonzo Church proved the same result using a completely different mathematical framework called lambda calculus. When Turing and Church compared notes, they realized their two approaches were equivalent. This became known as the Church-Turing Thesis: anything that can be computed by any reasonable computational process can be computed by a Turing Machine.
This is Theory of Computation. It does not ask "how fast is my CPU?" or "which programming language should I use?" It asks the deepest possible questions about computation itself.
Theory of Computation is organized around three foundational questions, each building on the last.
The first question asks about possibility, not speed. Given unlimited time and memory, can a computer even solve this problem in principle?
The surprising answer: most mathematical problems cannot be solved by any computer, no matter how powerful. The set of all possible problems is infinitely larger than the set of solvable ones. The Halting Problem — deciding whether an arbitrary program will eventually stop or run forever — is the most famous unsolvable problem. Turing proved its unsolvability in 1936 using a brilliant self-referential argument.
Some problems are undecidable: no algorithm can correctly answer yes or no for every possible input. This is not a limitation of current hardware or software — it is a mathematical impossibility. No future technology can overcome it.
This has real consequences. Software verification tools cannot, in general, prove that an arbitrary program is free of bugs. Email spam filters cannot perfectly classify every message. These are not engineering failures — they are mathematical certainties.
Among problems that are solvable, how much time and memory do they require? The famous P vs NP question asks whether problems whose solutions are verifiable quickly are also solvable quickly. This question, posed formally in 1971 by Stephen Cook, remains unsolved — and a $1,000,000 Millennium Prize awaits whoever answers it.
Modern cryptography depends on the assumption that P ≠ NP. If someone proved P = NP, every encrypted website, every secure transaction, every digital signature would become vulnerable overnight.
Theory of Computation is not abstract philosophy. Its fingerprints are on the software you use every day.
Regular expressions and DFA — every time you validate a form field, every time grep searches a file, a finite automaton is executing. The regex ^[0-9]{10}$ is literally a compiled DFA, running on your input string one character at a time.
Programming language parsers — every compiler (GCC, Clang, the Python interpreter) uses a context-free grammar to parse source code into an abstract syntax tree. When your IDE shows a red underline for a syntax error, a pushdown automaton found an invalid parse.
Cryptography — RSA encryption depends on the fact that multiplying two large primes is easy, but factoring their product is hard (no known polynomial-time algorithm). This is a complexity-theoretic result.
AI safety — Rice's Theorem, a generalization of the Halting Problem, proves that no algorithm can determine any non-trivial semantic property of an arbitrary program. This means certain program behaviors are provably unknowable without running the program — a fundamental constraint on AI safety verification systems.
Theory of Computation studies three nested families of machines, each more powerful than the last. These form the Chomsky Hierarchy, named after linguist Noam Chomsky who formalized it in 1956.
Each level is strictly contained within the one above it. Every regular language is also context-free, but not every context-free language is regular. And so on upward.
Alan Turing (1912–1954) deserves more than a footnote. His contributions define not just Theory of Computation but the entire intellectual foundation of computer science.
During World War II, Turing led the British codebreaking team at Bletchley Park that cracked the German Enigma cipher. Historians estimate this work shortened the war by two to four years and saved millions of lives. The electro-mechanical machines he built to break Enigma — called Bombes — were among the first special-purpose computing devices.
After the war, he formalized the concept of a stored-program computer (the Von Neumann architecture implemented his ideas), invented the Turing Test for machine intelligence in 1950, and pioneered mathematical biology with his work on morphogenesis.
In 1952, he was convicted under British law for "gross indecency" — a criminal charge for being gay. He was subjected to chemical castration as a condition of probation. He died in June 1954 from cyanide poisoning, ruled a suicide. He was 41 years old.
The United Kingdom issued a formal posthumous pardon in 2013. In 2021, Turing's face was placed on the British £50 note. It was not enough, but it was something.
The Church-Turing Thesis is not a theorem — it cannot be proved, because "computation" and "algorithm" are informal concepts. But it is the central working hypothesis of computer science:
Any function that is intuitively computable can be computed by a Turing Machine.
This thesis means that the Turing Machine is a universal model of computation. No matter what programming language you use, no matter what hardware you build, you cannot compute anything that a Turing Machine cannot compute. You might be faster or more convenient — but not more powerful in a fundamental sense.
Lambda calculus, recursive functions, RAM machines, cellular automata, DNA computing, quantum computing — all have been proven equivalent to Turing Machines in terms of what they can compute (though quantum computers have advantages in efficiency, not computability).
| Model | Language Class | Example Problem | Power Level | Real Application |
|---|---|---|---|---|
| Finite Automaton (DFA/NFA) | Regular | Does this string match [0-9]+? | Weakest | Regex engines, lexers |
| Pushdown Automaton (PDA) | Context-Free | Is this arithmetic expression balanced? | Moderate | Programming language parsers |
| Linear-Bounded Automaton | Context-Sensitive | Is this string a valid natural language sentence? | Strong | Natural language (approx.) |
| Turing Machine | Recursively Enumerable | Does this program eventually halt? | Strongest | Theoretical upper bound |
The rest of this course builds upward through the Chomsky Hierarchy, starting from the simplest model — the Deterministic Finite Automaton — and working toward the Turing Machine. Along the way, you will:
The mathematical machinery will get rigorous. But the questions — what can be computed, and at what cost? — are among the most profound in all of science.
Turing asked them at 24. Now it is your turn.
Get this course's notes on Telegram!
Free cheat sheets, summaries & practice exercises