Computation and Turing Machines
ver. 1.0.0
Origins and formalization of computation, Turing machines and undecidability, plus a compact history of programming languages and their paradigms
This node links the historical and technical origins of modern computation — from Babbage, Hilbert, and Gödel to Turing and Church — to precise models (Turing machines, lambda calculus), formal notions of decision problems and decidability, canonical undecidability proofs (Halting Problem, PCP), and a compact survey connecting theoretical machines to von Neumann hardware and major programming-language paradigms.
This unit synthesizes the emergence of computation as a rigorous mathematical concept with concrete machine models and practical programming-language history. It begins with the intellectual arc that made “computation” precise: mechanical ideas of Babbage and Lovelace; Hilbert’s call for a mechanical decision procedure; Gödel’s incompleteness showing limits of formal systems; and the independent formalisms of Turing’s machines and Church’s lambda calculus, whose equivalence underpins the Church–Turing thesis.
Building on that foundation, the material introduces Turing machines formally — states, tape, transition functions, configurations — and develops construction examples (erasing strings, recognizing regular languages, copying substrings, accepting non-context-free languages). It presents Universal Turing Machines and their role in simulation, compilation, and self-hosting systems. Complementary lecture material frames algorithms, computable functions, decidable and semidecidable languages, and contrasts TMs with simpler automata (DFAs, PDAs).
The node also explains decision problems: how to define instances and decision procedures, what it means for a problem to be decidable (an always-halting correct algorithm), and why some logical assertions expressible in first-order logic need not be decidable. It outlines the structure of undecidability proofs: adopt a precise model of algorithm, use countability/diagonalization and reductions, and give concrete unsolvable examples. Key proofs include the Halting Problem and acceptance/simulation undecidability, Post Correspondence Problem, and related constructions that show most problems are algorithmically unsolvable.
Finally, the course situates theory in computing history by tracing how abstract machines became physical via von Neumann’s EDVAC and surveying major programming-language paradigms: FORTRAN’s compiled numeric code, Lisp’s functional roots and garbage collection, C’s systems imperatives, Smalltalk and C++ for object-orientation, Haskell’s pure functional design, the proliferation of 1990s web/scripting languages, and SQL as a canonical DSL. Learners finishing this node should be able to explain the historical milestones, formal machine models, the meaning of decidability, and the canonical techniques and examples used to prove undecidability, while also recognizing how those theoretical ideas map to hardware and language paradigms.
Units
The Birth of Computation
How the modern, mathematical notion of computation arose and what it lets us prove
The Birth of Programming Languages
A rapid historical survey connecting von Neumann hardware to major programming-language paradigms from FORTRAN and Lisp through object-orientation, functional purity, 1990s web languages, and SQL.
The Limits of Computation
How to define decision problems, what decidability means, why not all logical assertions are decidable, and what a proof of undecidability requires
Basics of a Turing Machine
An instructional lecture slide deck introducing Turing Machines, their formal definition, construction examples, configurations, and Universal Turing Machines.
Algorithms and the Limits of Computation
A slide deck on the Theory of Computation exploring algorithmic solvability, Turing machine capabilities, undecidability proofs, and unsolvable problems like the Halting Problem and Post Correspondence Problem.