Computability Summary

Mathematical Logic · Axiom Academy

Let's review the fundamental limits of computation: what problems can be solved algorithmically, the halting problem, decidability hierarchies, and the deep connections between computation and logic. Turing Machines as Universal Model Formal definition: A Turing machine consists of an infinite tape, a read/write head, a finite set of states, and transition rules Simple yet powerful: Despite minimal components, Turing machines can compute anything any modern computer can compute Universal computation: There exists a universal Turing machine that can simulate any other Turing machine - the theoretical foundation of general-purpose computers Deterministic model: At each step, the current state and tape symbol uniquely determine the next action (write, move, change state) Why Turing machines matter: They provide a precise mathematical definition of "algorithm" and "computable function" Central claim: Any function that can be computed by any mechanical process can be computed by a Turing machine Not a theorem: Cannot be formally proved because "mechanical process" is informal - but universally accepted based on extensive evidence Equivalent models: Lambda calculus, recursive functions, register machines, modern programming languages - all compute the same class of functions Profound implication: There is a precise, objective notion of what is computable - computation has inherent limits independent of technology

This is the written version of the interactive lesson above. See the full Mathematical Logic course.