Understanding Computation
From Simple Machines to Impossible Programs
Publisher: O'Reilly Media
Final Release Date: May 2013
Pages: 332

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
Product Details
About the Author
Colophon
Recommended for You
Customer Reviews

REVIEW SNAPSHOT®

by PowerReviews
oreillyUnderstanding Computation
 
4.9

(based on 8 reviews)

Ratings Distribution

  • 5 Stars

     

    (7)

  • 4 Stars

     

    (1)

  • 3 Stars

     

    (0)

  • 2 Stars

     

    (0)

  • 1 Stars

     

    (0)

100%

of respondents would recommend this to a friend.

Pros

  • Well-written (8)
  • Helpful examples (7)
  • Accurate (6)
  • Concise (5)
  • Easy to understand (5)

Cons

    Best Uses

    • Intermediate (6)
    • Student (6)
    • Novice (5)
      • Reviewer Profile:
      • Developer (4), Educator (3)

    Reviewed by 8 customers

    Sort by

    Displaying reviews 1-8

    Back to top

     
    5.0

    Excellent tutorial

    By pmc

    from UK

    About Me Interested Amateur

    Verified Reviewer

    Pros

    • Accurate
    • Concise
    • Easy to understand
    • Helpful examples
    • Well-written

    Cons

      Best Uses

      • Intermediate
      • Student

      Comments about oreilly Understanding Computation:

      I have a curiosity and interest in programming, programming languages, computers and computer science but no formal education in any of those and no particular talent for mathematics either.

      This book is as close as I can get to having a real insight into the fundamental concepts and theories of computation that up until now were always completely impenetrable to me.

      I was aware of Ruby but had never read any Ruby code although I have written code in several other languages and I think that experience plus the book's own whirlwind tour of Ruby definitely helped when reading this book. I'm not sure if this book would be immediately accessible to anyone without that type of experience but, to be fair, the book is specifically aimed at programmers so most readers should have no trouble.

      Overall a great book, well written and very much enjoyed by me.

       
      5.0

      Fun introduction to computational theory

      By babelfish007

      from Charleston, SC

      About Me Alzheimer's Researcher, Educator

      Verified Buyer

      Pros

      • Accurate
      • Concise
      • Helpful examples
      • Well-written

      Cons

        Best Uses

        • Intermediate
        • Novice
        • Student

        Comments about oreilly Understanding Computation:

        I am not a professional programmer or computer scientist, but I am a scientist and I do program. In the past, I read and enjoyed Michael Sipser's book "Introduction to the Theory of Computation," but didn't attempt the exercises or force myself to really understand the proofs. I found this book to be better for casual reading than Sipser's book (which is actually an undergraduate-level textbook). In order to make sure I was "getting" the Ruby code, I translated nearly everything from Chapter 2 (on finite state machines) into Python and I would like to do the same with the section on the lambda calculus. The idea of using a working, popular, and readable programming language to exhibit the ideas was a stroke of genius. Although, I happen not to use Ruby, I still found nearly every code example to be lucid and concise.

        My favorite thing about the book is that it goes beyond just discussing Turing machines and gives details about several other Turing-complete systems, sketching out ways of proving their Turing-completeness. The author covers the lambda calculus, the SKI calculus, Iota (mind bending), and tag systems. The whole thing is delivered in clear, conversational prose.

        As someone who deals as much with natural language as with programming languages, I would have liked to have seen some discussion of natural language parsers or the computational complexity of natural language. However, I can see how these things could be considered to be outside the scope of the book.

        If you have to take a course on computational theory or you are planning to read Sipser or Hopcroft and Ullman, this book would make a great appetizer.

        (4 of 4 customers found this review helpful)

         
        5.0

        Best book on a technical subject ever.

        By Rewards program

        from Philadelphia

        About Me Developer, Educator

        Verified Reviewer

        Pros

        • Accurate
        • Concise
        • Easy to understand
        • Helpful examples
        • Well-written

        Cons

          Best Uses

          • Intermediate
          • Novice
          • Student

          Comments about oreilly Understanding Computation:

          I taught myself to program a year ago so there are huge gaps in my knowledge. This book is so clearly written that I had no trouble keeping up even though the concepts are complex and abstract. The authors do a great job illustrating abstract ideas with concrete ruby implementations. Shortly after reading it I started developing a single page JavaScript web app and found myself effortlessly incorporating ideas from the book. This book is great for anyone interested in formal systems theories, not just programmers. I wish the authors would write a book on every subject I want to learn about..

          (3 of 3 customers found this review helpful)

           
          5.0

          Theoretical Approach in Computer Science

          By tribalia

          from Bucharest, Romania

          About Me Developer

          Verified Reviewer

          Pros

          • Accurate
          • Concise
          • Easy to understand
          • Helpful examples
          • Well-written

          Cons

            Best Uses

            • Novice

            Comments about oreilly Understanding Computation:

            A serious programmer needs to read this book. A real programmer is a philosopher. Tom Stuart makes a great job explaining the concepts of the computer sience.

            (6 of 6 customers found this review helpful)

             
            5.0

            Lucid and enjoyable

            By Martin Kleppmann

            from London, UK

            About Me Developer

            Verified Reviewer

            Pros

            • Delightful
            • Helpful examples
            • Well-written

            Cons

              Best Uses

              • Intermediate
              • Student

              Comments about oreilly Understanding Computation:

              "Understanding Computation" is the most lucid, clear and enjoyable to read explanation of theoretical computer science that I have seen. It covers a remarkably large amount of material, but explains it very logically, step by step, so it is nevertheless easy to follow.

              The style is very hands-on (every example is implemented in short snippets of Ruby), completely different from the dry, academic presentation in most textbooks.

              The book says it's aimed at programmers without a formal background in theoretical computer science. That said, I have studied a reasonable amount of CS, and I learnt a lot from this book. More importantly, reading it was *delightful*. I think this is a book you should read for pleasure, not for work, to discover the beauty behind the machines we work with every day.

              (5 of 5 customers found this review helpful)

               
              5.0

              Extremely accessible and engaging

              By James

              from Austin, TX

              About Me Developer, Maker

              Verified Reviewer

              Pros

              • Accurate
              • Easy to understand
              • Engaging
              • Helpful examples
              • Often Funny
              • Well-written

              Cons

                Best Uses

                • Expert
                • Intermediate
                • Novice
                • Student

                Comments about oreilly Understanding Computation:

                Rather than anything like a textbook, Understanding Computation is a guided tour of some of the most interesting and fundamental aspects of computation, presented in a way that doesn't rely on dry theoretical proofs or hard-to-follow mathematical explanations.

                The author uses a high level programming language to demonstrate some simple systems that demonstrate interesting computational principles, making this a really excellent text for those who have entered the world of computing from backgrounds other than computer science. However, even if you are familiar with the concepts the book is still a delight to read, thanks to the author's clear and engaging style, thorough examples (all of which have made available to download and experiment with yourself). Even if you consider yourself a computer science expert and already know about everything the book covers, I am confident that you'll enjoy taking this journey.

                I really cannot recommend this enough; if you have any curiosity at all about what a Turing machine is, and what makes it special, this book will answer those questions and leave you ready and eager to learn more.

                (4 of 10 customers found this review helpful)

                 
                4.0

                understanding computing

                By WD

                from jakarta, indonesia

                About Me Sys Admin

                Verified Reviewer

                Pros

                • Concise
                • Well-written

                Cons

                  Best Uses

                  • Novice

                  Comments about oreilly Understanding Computation:

                  it is quite useful . technical but not so technical that it makes me want to stop reading it.

                  (10 of 10 customers found this review helpful)

                   
                  5.0

                  Excellent

                  By Casiano

                  from Tenerife. Spain

                  About Me Educator

                  Verified Reviewer

                  Pros

                  • Accurate
                  • Easy to understand
                  • Helpful examples
                  • Well-written

                  Cons

                    Best Uses

                    • Intermediate
                    • Student

                    Comments about oreilly Understanding Computation:

                    The fundamentals ideas of Theoretical Computer Science in a language that most programmers will find engaging and practical: using real code. It is not only ideal for students following introductory courses in Computability, Automata Theory, Formal Semantics, Lambda Calculus, etc. but also for lecturers preparing the material for such courses and for programmers with no background in Computer Science. I will certainly include it in the bibliography of any of my "Introduction to Computability" courses.

                    Displaying reviews 1-8

                    Back to top

                     
                    Buy 2 Get 1 Free Free Shipping Guarantee
                    Buying Options
                    Immediate Access - Go Digital what's this?
                    Ebook: $33.99
                    Formats:  DAISY, ePub, Mobi, PDF
                    Print & Ebook: $43.99
                    Print: $39.99