You are previewing Understanding Computation.
O'Reilly logo
Understanding Computation

Book Description

Finally, you can learn computation theory and programming language design in an engaging, practical way. Understanding Computation explains theoretical computer science in a context you’ll recognize, helping you appreciate why these ideas matter and how they can inform your day-to-day programming.

Table of Contents

  1. Special Upgrade Offer
  2. Preface
    1. Who Should Read This Book?
    2. Conventions Used in This Book
    3. Using Code Examples
    4. Safari® Books Online
    5. How to Contact Us
    6. Acknowledgments
  3. 1. Just Enough Ruby
    1. Interactive Ruby Shell
    2. Values
      1. Basic Data
      2. Data Structures
      3. Procs
    3. Control Flow
    4. Objects and Methods
    5. Classes and Modules
    6. Miscellaneous Features
      1. Local Variables and Assignment
      2. String Interpolation
      3. Inspecting Objects
      4. Printing Strings
      5. Variadic Methods
      6. Blocks
      7. Enumerable
      8. Struct
      9. Monkey Patching
      10. Defining Constants
      11. Removing Constants
  4. I. Programs and Machines
    1. 2. The Meaning of Programs
      1. The Meaning of “Meaning”
      2. Syntax
      3. Operational Semantics
        1. Small-Step Semantics
          1. Expressions
          2. Statements
          3. Correctness
          4. Applications
        2. Big-Step Semantics
          1. Expressions
          2. Statements
          3. Applications
      4. Denotational Semantics
        1. Expressions
        2. Statements
        3. Applications
      5. Formal Semantics in Practice
        1. Formality
        2. Finding Meaning
        3. Alternatives
      6. Implementing Parsers
    2. 3. The Simplest Computers
      1. Deterministic Finite Automata
        1. States, Rules, and Input
        2. Output
        3. Determinism
        4. Simulation
      2. Nondeterministic Finite Automata
        1. Nondeterminism
        2. Free Moves
      3. Regular Expressions
        1. Syntax
        2. Semantics
        3. Parsing
      4. Equivalence
    3. 4. Just Add Power
      1. Deterministic Pushdown Automata
        1. Storage
        2. Rules
        3. Determinism
        4. Simulation
      2. Nondeterministic Pushdown Automata
        1. Simulation
        2. Nonequivalence
      3. Parsing with Pushdown Automata
        1. Lexical Analysis
        2. Syntactic Analysis
        3. Practicalities
      4. How Much Power?
    4. 5. The Ultimate Machine
      1. Deterministic Turing Machines
        1. Storage
        2. Rules
        3. Determinism
        4. Simulation
      2. Nondeterministic Turing Machines
      3. Maximum Power
        1. Internal Storage
        2. Subroutines
        3. Multiple Tapes
        4. Multidimensional Tape
      4. General-Purpose Machines
        1. Encoding
        2. Simulation
  5. II. Computation and Computability
    1. 6. Programming with Nothing
      1. Impersonating the Lambda Calculus
        1. Working with Procs
          1. Plumbing
          2. Arguments
          3. Equality
          4. Syntax
        2. The Problem
        3. Numbers
        4. Booleans
        5. Predicates
        6. Pairs
        7. Numeric Operations
        8. Lists
        9. Strings
        10. The Solution
        11. Advanced Programming Techniques
          1. Infinite streams
          2. Avoiding arbitrary recursion
      2. Implementing the Lambda Calculus
        1. Syntax
        2. Semantics
          1. Replacing variables
          2. Calling functions
          3. Reducing expressions
        3. Parsing
    2. 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. 8. Impossible Programs
      1. The Facts of Life
        1. Universal Systems Can Perform Algorithms
        2. Programs Can Stand In for Turing Machines
        3. Code Is Data
        4. Universal Systems Can Loop Forever
        5. Programs Can Refer to Themselves
      2. Decidability
      3. The Halting Problem
        1. Building a Halting Checker
        2. It’ll Never Work
          1. Too good to be true
          2. Fundamentally impossible
      4. Other Undecidable Problems
      5. Depressing Implications
      6. Why Does This Happen?
      7. Coping with Uncomputability
    4. 9. Programming in Toyland
      1. Abstract Interpretation
        1. Route Planning
        2. Abstraction: Multiplying Signs
        3. Safety and Approximation: Adding Signs
      2. Static Semantics
        1. Implementation
        2. Benefits and Limitations
      3. Applications
  6. A. Afterword
  7. Index
  8. About the Author
  9. Colophon
  10. Special Upgrade Offer
  11. Copyright