Theory of Computation

Theory of computation steps back from the engineering practice of the previous topic to ask a more fundamental question: not how to build software well, but what any computer, built with any amount of skill, can actually compute at all. An automaton is an abstract machine that reads input symbol by symbol and moves between a fixed set of states as it reads, and the simplest kind, a finite automaton, already appeared physically earlier in this series without being named: a register or any sequential circuit from the digital-logic topic is exactly a tiny automaton, its current state built from flip-flops and its transitions wired as logic gates. A formal language is the precise set of input strings a given automaton accepts — a finite automaton can recognize surprisingly structured languages, like "all strings that end in 01," but there are languages no finite automaton can ever recognize no matter how many states it is given, because a finite automaton cannot count arbitrarily high or remember arbitrarily much, which is exactly the limitation a Turing machine was invented to remove by adding unlimited memory it can read, write, and move across freely. Computability is the question of what a Turing machine can compute given enough time and memory, and it turns out to be a remarkably stable boundary: every real programming language, every CPU described in the computer-architecture topic, and every Turing machine can all compute exactly the same set of problems, differing only in convenience and speed, never in what is fundamentally reachable. Decidability asks a sharper question: is there even an algorithm that can correctly answer a given yes-or-no question for every possible input? The most famous result in this entire field is that the answer is sometimes no — the halting problem, "will this specific program eventually stop running or loop forever," has been mathematically proven to have no general algorithmic solution at all, a hard ceiling no amount of the previous topic's testing or engineering discipline can ever climb past for every possible program. Complexity classes return to a question algorithm analysis already asked for one algorithm — how expensive is this — but now ask it about an entire problem itself, independent of any specific algorithm: P is the class of problems solvable quickly (in polynomial time), NP is the class of problems whose proposed solution can at least be checked quickly even if finding one might not be, and whether every problem in NP secretly belongs to P too is the open P versus NP question, one of the most famous unsolved problems in all of mathematics. This series now has a complete answer to three different questions about any piece of software: what can it compute at all (computability), can a correct answer always be found algorithmically (decidability), and how expensive is it to find one (complexity) — and the next topic, programming languages and compilers, is what actually turns an algorithm a programmer writes into instructions a real Turing-machine-equivalent CPU can execute.

A Finite Automaton, Recognizing One Language Accepts every string that ends in 01 — nothing else start state A state B state C accept 0 1 1 0 0, resets the count toward an ending 01 a flip-flop from digital logic is already a one-bit version of exactly this: a fixed set of states, transitioning on each input, nothing more
Two Hard Limits on Computing Itself Not bugs to fix — proven, permanent boundaries Decidability: the halting problem "will this program eventually stop, or run forever?" proven: no algorithm can answer this correctly for every program Complexity: P vs. NP P: solvable quickly NP: a solution checks quickly, even if finding one might not still open: is every NP problem secretly also in P? Three separate questions, three separate topics in this series computability: can it be computed at all (this topic) decidability: can an algorithm always find the answer (this topic) complexity: how expensive is finding it (algorithm analysis, revisited here)

Take theory of computation further

Ask the copilot about this term, or have our engineers assess it against your process.

Ask CFSGPT about this → Request a technical assessment → Open the CFS app