Books & Videos

Table of Contents

  1. Chapter 1 Just Enough Ruby

    1. Interactive Ruby Shell

    2. Values

    3. Control Flow

    4. Objects and Methods

    5. Classes and Modules

    6. Miscellaneous Features

  2. Programs and Machines

    1. Chapter 2 The Meaning of Programs

      1. The Meaning of “Meaning”
      2. Syntax
      3. Operational Semantics
      4. Denotational Semantics
      5. Formal Semantics in Practice
      6. Implementing Parsers
    2. Chapter 3 The Simplest Computers

      1. Deterministic Finite Automata
      2. Nondeterministic Finite Automata
      3. Regular Expressions
      4. Equivalence
    3. Chapter 4 Just Add Power

      1. Deterministic Pushdown Automata
      2. Nondeterministic Pushdown Automata
      3. Parsing with Pushdown Automata
      4. How Much Power?
    4. Chapter 5 The Ultimate Machine

      1. Deterministic Turing Machines
      2. Nondeterministic Turing Machines
      3. Maximum Power
      4. General-Purpose Machines
  3. Computation and Computability

    1. Chapter 6 Programming with Nothing

      1. Impersonating the Lambda Calculus
      2. Implementing the Lambda Calculus
    2. Chapter 7 Universality Is Everywhere

      1. Lambda Calculus
      2. Partial Recursive Functions
      3. SKI Combinator Calculus
      4. Iota
      5. Tag Systems
      6. Cyclic Tag Systems
      7. Conway’s Game of Life
      8. Rule 110
      9. Wolfram’s 2,3 Turing Machine
    3. Chapter 8 Impossible Programs

      1. The Facts of Life
      2. Decidability
      3. The Halting Problem
      4. Other Undecidable Problems
      5. Depressing Implications
      6. Why Does This Happen?
      7. Coping with Uncomputability
    4. Chapter 9 Programming in Toyland

      1. Abstract Interpretation
      2. Static Semantics
      3. Applications
  1. Appendix Afterword

  2. Colophon