Free online textbook 'Theory of Computing: An Open Introduction' by Taylor J. Smith
burkov · x · 2026-11-17
Taylor J. Smith's free 2024 online textbook Theory of Computing: An Open Introduction is an undergraduate-focused introduction to what computation can and cannot do.
- Organized around a progression in computational power: regular expressions and finite automata (regular languages), then context-free grammars and pushdown automata, then Turing machines with tape-based memory.
- Each stage relates different representations of the same language, develops constructions to translate between models, and identifies the limits that remain.
- Builds toward the Chomsky hierarchy and the distinctions among regular, context-free, decidable, and semidecidable languages.
More from Research
- Grant project seeks $5K–$20K to study how agent personalities shape their societies in OHOL — sebkrier · 2026-11-17
- A Pharma Agent That Flags Developability Risks on Every Sequence Registration — nlarusstone · 2026-11-17
- After CoRL, roboticists debate where agentic robotics breaks: sim, dexterity, repeatability — k7agar · 2026-11-17
- Polyak–Lojasiewicz paper 10-year retrospective published, wins 2026 KDD Test of Time award — jasondeanlee · 2026-11-17
- Microsoft Details Maia Dataflow Architecture: 4719 Tflop/s fp8, Over 99% of Peak — thoefler · 2026-11-17
- Ternary Moral Logic: A Proposal for Hardware-Enforced AI Pause and Accountability — MoralLogs · 2026-11-17