O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Understanding Computation

Understanding Computation

by Tom Stuart
Publisher: O'Reilly Media, Inc.
Release Date: May 2013
ISBN: 9781449330071
View table of contents
Start reading

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.

Rather than use mathematical notation or an unfamiliar academic programming language like Haskell or Lisp, this book uses Ruby in a reductionist manner to present formal semantics, automata theory, and functional programming with the lambda calculus. It’s ideal for programmers versed in modern languages, with little or no formal training in computer science.

  • Understand fundamental computing concepts, such as Turing completeness in languages
  • Discover how programs use dynamic semantics to communicate ideas to machines
  • Explore what a computer can do when reduced to its bare essentials
  • Learn how universal Turing machines led to today’s general-purpose computers
  • Perform complex calculations, using simple languages and cellular automata
  • Determine which programming language features are essential for computation
  • Examine how halting and self-referencing make some computing problems unsolvable
  • Analyze programs by using abstract interpretation and type systems

Table of Contents

  1. 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
  2. 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
  3. 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
  4. 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
  5. A. Afterword
  6. Index
  7. About the Author
  8. Colophon
  9. Copyright