Contents
-
Preface — What is this book for? Who should read this book? What is Ruby?
- Who Should Read This Book?
- Conventions Used In This Book
- Using Code Examples
- Acknowledgments
-
Chapter 1: Just Enough Ruby
- Interactive Ruby Shell
- Values
- Control Flow
- Objects and Methods
- Classes and Modules
- Miscellaneous Features
-
Part 1: Programs and Machines
-
Chapter 2: The Meaning of Programs (PDF) — What is a programming language? When we write a program, how do we know what it means, and how does the computer know?
- The Meaning of “Meaning”
- Syntax
- Operational Semantics
- Denotational Semantics
- Formal Semantics in Practice
- Implementing Parsers
-
Chapter 3: The Simplest Computers — What does the simplest possible computer look like? What can it be used for? How powerful is it?
- Deterministic Finite Automata
- Nondeterministic Finite Automata
- Regular Expressions
- Equivalence
-
Chapter 4: Just Add Power — How can we make a simple computer more powerful? What can we do with it? How much more powerful can it get?
- Deterministic Pushdown Automata
- Nondeterministic Pushdown Automata
- Parsing with Pushdown Automata
- How Much Power?
-
Chapter 5: The Ultimate Machine — What does the most powerful computer look like? How simple is it? How can we program it?
- Deterministic Turing Machines
- Nondeterministic Turing Machines
- Maximum Power
- General-Purpose Machines
-
Part II: Computation and Computability
-
Chapter 6: Programming with Nothing (video, article) — How many features does a programming language need? How much work can a language do if we remove all of its features?
- Impersonating the Lambda Calculus
- Implementing the Lambda Calculus
-
Chapter 7: Universality Is Everywhere — Can a simple system do as much as the most powerful computer? How simple is it possible to get?
- Lambda Calculus
- Partial Recursive Functions
- SKI Combinator Calculus
- Iota
- Tag Systems
- Cyclic Tag Systems
- Conway’s Game of Life
- Rule 110
- Wolfram’s 2,3 Turing Machine
-
Chapter 8: Impossible Programs (video) — What jobs can programs do? How do they do them? What jobs are impossible for any program to do?
- The Facts of Life
- Decidability
- The Halting Problem
- Other Undecidable Problems
- Depressing Implications
- Why Does This Happen?
- Coping with Uncomputability
-
Chapter 9: Programming in Toyland — How can programs handle difficult or impossible problems? How do programs cope with incomplete or contradictory information?
- Abstract Interpretation
- Static Semantics
- Applications