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
 GeneralPurpose 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