What do you think?
Rate this book
Understanding Computation: From Simple Machines to Impossible Programs
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
About the Author
Tom Stuart is a computer scientist and programmer, and the founder of Codon, a digital product consultancy in London. He works as a consultant, mentor and trainer, helping companies to improve the quality and clarity of their approach to creating software products, usually on the web. He has lectured on optimizing compilers at the University of Cambridge, co-organizes the Ruby Manor conference, and is a member of the London Ruby User Group.
352 pages, Paperback
First published January 1, 2013
85 people are currently reading
1633 people want to read
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 29 of 29 reviews
July 7, 2013
Despite the fact that there's no real reason to be apologetic, I also haven't yet reached the point in my career as a software developer where I've stopped apologizing for the fact that I have no "real" Computer Science Background.[^1] And/but that's exactly what draws me to books like Understanding Computation by Tom Stuart (O'Reilly, 2013). Stuart describes the books as for:
In other words, people like me. The people that Eric Miraglia described as the "liberal arts majors drafted into web-developer service during the dotcom boom".[^2] Yes: the liberal artsy non-computer science degree holders that wound up doing computer sciencey type software work just the same. Smart people that nevertheless are exploring some of these concepts for the first time.
For a taste of what I mean, observe the following quote:
If that made you smile just a little bit, because you want to peel the onion layers away and get at the semantic questions underneath... then this book is for you.
Now before we go any further -- a couple words on what this book is not. This is not a book about software engineering. "Big O notation" does not make an appearance here in the text, not once. It isn't that we aren't concerned with "clean code" or efficiency or scalability or any of that -- but those are just implementation details that are not particularly interesting when you're otherwise diving into language semantics and finite automata.
Instead, the kind of questions this book poses are more like:
- What is a computer?
- How do you create one?
- How does a computer compute?
- How would you go about designing a language?
- Are there limits to computation? What are they?
These are fascinating questions, and reading this book was one of the first times where I really understood what separates "computer science" from "software engineering". The book is a fascinating read, even if it occasionally lapses into sentences like this:
Awesome, but a little opaque.[^3] And/but, there's quite a bit of this; for a "simple" book about foundational computer science thinking, there's a lot of complicated material. ("But this is why you're here, right? To dip your toes into this particular pool?") It's often challenging, but also rewarding. (And there's plenty of humor along the way, if you're paying attention.)
A year from now, when I'm settling in to re-read this one, I probably won't remember the details about pushdown automata or what formalisms define a "universal Turing machine". However, I'm going to remember the in-depth discussions of static typing vs. dynamism and the trade-offs between them. I'll remember that we went through some engrossing exercises where we built up integers and arithmetic operators from scratch (even if I don't remember the details). I'll remember the flirtatious foray into language design. I'll remember The Halting Problem and most of the gory details around the limits of computation. And another thing I'll remember, statements like this:
If you're "doing software" and you don't have a degree in computer science, I'm going to urge you to read this book. Even if you can't follow everything, you'll walk away with a lot of insight. (I'm particularly fond of the first and last thirds.) And if you do have a CS degree... Well, it's still worth skimming.
[^1]: The "full disclosure" footnote: I was briefly declared as a computer science major while in college. I performed... serviceably in an intro class (Common Lisp!) and in an "intro to AI" class (more Lisp!) but got ground to a frustrating halt in "Programming and Data Structures". I blamed Dr. Hunter, but I think I just wasn't ready to think that way. Call me a late bloomer. Call me a self-learner. Call me a frustrating bastard.
[^2]: That quote can be attributed to Miraglia's foreword to the second edition of Nicholas Zakas' Professional JavaScript for Web Developers (2nd ed.). The book is in its third edition now -- and I highly recommend that edition -- and/but: come on, that's a fantastic quote, and is the reason that the two editions will co-habitate on my bookshelf for as long as the bindings hold together.
[^3]: Partly my own fault for doing so much of the reading as my too-late-night bedtime reading.
---
A version of this review also appears on my blog: blog.founddrama.net/2013/07/review-understanding-computation/
...programmers who are curious about programming languages and the theory of computation, especially those who don’t have a formal background in mathematics or computer science.
In other words, people like me. The people that Eric Miraglia described as the "liberal arts majors drafted into web-developer service during the dotcom boom".[^2] Yes: the liberal artsy non-computer science degree holders that wound up doing computer sciencey type software work just the same. Smart people that nevertheless are exploring some of these concepts for the first time.
For a taste of what I mean, observe the following quote:
In the end, syntax is only concerned with the surface appearance of programs, not with their meanings.
If that made you smile just a little bit, because you want to peel the onion layers away and get at the semantic questions underneath... then this book is for you.
Now before we go any further -- a couple words on what this book is not. This is not a book about software engineering. "Big O notation" does not make an appearance here in the text, not once. It isn't that we aren't concerned with "clean code" or efficiency or scalability or any of that -- but those are just implementation details that are not particularly interesting when you're otherwise diving into language semantics and finite automata.
Instead, the kind of questions this book poses are more like:
- What is a computer?
- How do you create one?
- How does a computer compute?
- How would you go about designing a language?
- Are there limits to computation? What are they?
These are fascinating questions, and reading this book was one of the first times where I really understood what separates "computer science" from "software engineering". The book is a fascinating read, even if it occasionally lapses into sentences like this:
The NFA class automatically takes account of free moves — we can see that when our NFA is started in state 3, it’s already possible for it to be in state 2 or 3 before it has read any input — so we won’t need to do anything special in NFASimulation to support them.
Awesome, but a little opaque.[^3] And/but, there's quite a bit of this; for a "simple" book about foundational computer science thinking, there's a lot of complicated material. ("But this is why you're here, right? To dip your toes into this particular pool?") It's often challenging, but also rewarding. (And there's plenty of humor along the way, if you're paying attention.)
A year from now, when I'm settling in to re-read this one, I probably won't remember the details about pushdown automata or what formalisms define a "universal Turing machine". However, I'm going to remember the in-depth discussions of static typing vs. dynamism and the trade-offs between them. I'll remember that we went through some engrossing exercises where we built up integers and arithmetic operators from scratch (even if I don't remember the details). I'll remember the flirtatious foray into language design. I'll remember The Halting Problem and most of the gory details around the limits of computation. And another thing I'll remember, statements like this:
The purpose of an expression is to be evaluated to produce another expression; a statement, on the other hand, is evaluated to make some change to the state of the abstract machine.
If you're "doing software" and you don't have a degree in computer science, I'm going to urge you to read this book. Even if you can't follow everything, you'll walk away with a lot of insight. (I'm particularly fond of the first and last thirds.) And if you do have a CS degree... Well, it's still worth skimming.
[^1]: The "full disclosure" footnote: I was briefly declared as a computer science major while in college. I performed... serviceably in an intro class (Common Lisp!) and in an "intro to AI" class (more Lisp!) but got ground to a frustrating halt in "Programming and Data Structures". I blamed Dr. Hunter, but I think I just wasn't ready to think that way. Call me a late bloomer. Call me a self-learner. Call me a frustrating bastard.
[^2]: That quote can be attributed to Miraglia's foreword to the second edition of Nicholas Zakas' Professional JavaScript for Web Developers (2nd ed.). The book is in its third edition now -- and I highly recommend that edition -- and/but: come on, that's a fantastic quote, and is the reason that the two editions will co-habitate on my bookshelf for as long as the bindings hold together.
[^3]: Partly my own fault for doing so much of the reading as my too-late-night bedtime reading.
---
A version of this review also appears on my blog: blog.founddrama.net/2013/07/review-understanding-computation/
October 22, 2013
Simply put: it's a great book.
It goes over various things in theory of computation. I really like both the depth and the presentation.
Unlike a "Math for Programmers" book I read recently, this one is not shallow. It goes deep enough into all its subjects (automata, state machines, Turing machines, lambda calculus, types, and so on). Things don't just get overviewed – you get enough details to appreciate how those things actually work and what they are used for. Furthermore, every single abstracting is backed up by code. You can copy it and run it and see how the abstractions behave by themselves. I personally ended up implementing a bunch of the examples in order to get a better sense of them. Particularly, Brzozowski's algorithm for minimizing a finite automata was so perplexing, that I felt I had to witness it actually working. I even wrote some code that generates GraphViz files in order to visualize the DFA. This alone speaks how engaging this book is.
I greatly recommend it to the professional programmer. If you're deep into Computer Science, you'll only get a refresher. But if you're not, you're likely to experience a lot of fascination with this curious subject.
It goes over various things in theory of computation. I really like both the depth and the presentation.
Unlike a "Math for Programmers" book I read recently, this one is not shallow. It goes deep enough into all its subjects (automata, state machines, Turing machines, lambda calculus, types, and so on). Things don't just get overviewed – you get enough details to appreciate how those things actually work and what they are used for. Furthermore, every single abstracting is backed up by code. You can copy it and run it and see how the abstractions behave by themselves. I personally ended up implementing a bunch of the examples in order to get a better sense of them. Particularly, Brzozowski's algorithm for minimizing a finite automata was so perplexing, that I felt I had to witness it actually working. I even wrote some code that generates GraphViz files in order to visualize the DFA. This alone speaks how engaging this book is.
I greatly recommend it to the professional programmer. If you're deep into Computer Science, you'll only get a refresher. But if you're not, you're likely to experience a lot of fascination with this curious subject.
October 27, 2013
While most computer science students will already know the gist of this material, I found this to be a great refresher that also highlighted some other connections I had missed while learning the concepts in a purely academic setting. Stuart's use of Ruby definitely makes the material more approachable, as the semantics of Ruby are perhaps more intuitive to most developers than abstract mathematical notation.
Definitely would recommend for any Rubyist interested in either reacquainting themselves with computational theory, or are looking to get a better understanding than the one they hurriedly tried to acquire with an overworked course load.
Definitely would recommend for any Rubyist interested in either reacquainting themselves with computational theory, or are looking to get a better understanding than the one they hurriedly tried to acquire with an overworked course load.
November 10, 2021
I have already studied all the content of this book in the College with the "Introduction to the Theory of Computation" book from Michael Sipser a long time ago. Those books are very similar in the content but Sipser's book is focused on theory and how to prove things. Stuart's book focused on explaining the theory with the help of a high-level programming language (Ruby) so it is a little bit easier to understand. Although it is more practical than its counterpart, it also contains a lot of theory that is hard to use in the real world so it is not a book I can recommend for everyone because the major part of programmers I know would think it a lit bit boring or not practical.
This book goes to the basics of computing. It does not mean it is easier to understand. Think about the difference between Assembly and JavaScript. Assembly is simpler, it has much fewer rules and edge cases, but for most programmers, it is harder to understand.
This book constructs a lot of different models like Deterministic and NonDeterministic Finite Automata (DFA and NFA), Deterministic and Nondeterministic Pushdown Automata (DPDA and NPDA) a Turing Machine (TM), and a lot of other Turing-complete models like Lamda Calculus and many others. It also compares the power of each model and how determinism and other features can or cannot increment their power. When possible, it also translates logic from one model to another to show they are equivalent in computational power. It is not proof in a mathematical sense, but it is much easier to understand when you had finished College a long time ago or if you have no Computer Science background. It also implements a simple type system to show some difficulties and trade-offs the programming designers should make.
Finally, it also talks about the limits of computation. What types of problems it cannot solve and why. It uses a technique very similar to what was used in the book "Godel, Escher, Bach" to explain Godel Incompleteness Theorem.
It has a git repository very well documented. Its README has links between chapters of the book and the repository code some of them with tests (which is very rare).
This book goes to the basics of computing. It does not mean it is easier to understand. Think about the difference between Assembly and JavaScript. Assembly is simpler, it has much fewer rules and edge cases, but for most programmers, it is harder to understand.
This book constructs a lot of different models like Deterministic and NonDeterministic Finite Automata (DFA and NFA), Deterministic and Nondeterministic Pushdown Automata (DPDA and NPDA) a Turing Machine (TM), and a lot of other Turing-complete models like Lamda Calculus and many others. It also compares the power of each model and how determinism and other features can or cannot increment their power. When possible, it also translates logic from one model to another to show they are equivalent in computational power. It is not proof in a mathematical sense, but it is much easier to understand when you had finished College a long time ago or if you have no Computer Science background. It also implements a simple type system to show some difficulties and trade-offs the programming designers should make.
Finally, it also talks about the limits of computation. What types of problems it cannot solve and why. It uses a technique very similar to what was used in the book "Godel, Escher, Bach" to explain Godel Incompleteness Theorem.
It has a git repository very well documented. Its README has links between chapters of the book and the repository code some of them with tests (which is very rare).
November 22, 2016
This book is excellent and delivers on exactly what the description says: "for (Ruby) programmers versed in modern languages, with little or no formal training in computer science". The examples are built up fairly well, given the topic. I was a little surprised at what "computation theory" really meant, so reading it in the context of book club with people who do have more formal training was quite helpful in answering my questions of "but what is the point of this" (usually the answer is: if we can show these things are equivalent, we can do mathy proofs on properties of one that apply to the other, and different kinds of properties are easier to prove with different setups). Probably much less directly practical than other programming books I've rated as 5 stars, but it's just well-done and I feel more confident in knowing a bit more of the theory.
September 15, 2014
Although anybody with a formal CS education will be familiar with most of the theory in the book, it was a fun read, containing lots of example code and interesting experiments. If you are curious to see FizzBuzz implemented in lambda calculus (the solution with Ruby procs is included, spanning over nearly 5 pages) or an overview of a few interesting universal systems, give this book a try.
March 30, 2022
What book did I use for my Theory of Computation course? I don't remember. It was that (un)memorable. What did I learn in that course? Besides the Pigeonhole Principle... not much. It was a required course, so we had to take it. You'd think a required course would teach something useful, right? Well...
If Understanding Computation book had been my textbook for that course, I might have learned something. For starters, I didn't know Ruby before picking up this book, but the exposition at the beginning is just enough to get started. And then off we go: What is a program? What is a computer? How do you describe the two? What is the Lambda Calculus? What can you not program?
By itself, the book shouldn't work as a textbook since there aren't any exercises in it. Instead, the entire book is an exercise in simulating the theoretical things you would normally only read or reason about. More importantly, all the code still works! In that respect, this book holds up way better than Programming Collective Intelligence.
Recommended for anyone who wasn't a computer science major but somehow wound up in tech.
If Understanding Computation book had been my textbook for that course, I might have learned something. For starters, I didn't know Ruby before picking up this book, but the exposition at the beginning is just enough to get started. And then off we go: What is a program? What is a computer? How do you describe the two? What is the Lambda Calculus? What can you not program?
By itself, the book shouldn't work as a textbook since there aren't any exercises in it. Instead, the entire book is an exercise in simulating the theoretical things you would normally only read or reason about. More importantly, all the code still works! In that respect, this book holds up way better than Programming Collective Intelligence.
Recommended for anyone who wasn't a computer science major but somehow wound up in tech.
April 27, 2020
This book is excellent. Learn about computer science and about Ruby programming at the same time. It's very approachable, very fun, and very mind-bendy. I had to pause it when live dragged me away enough that I couldn't give it the attention it deserved, but I absolutely will return to it later.
I think it makes a great third Ruby book to read; choose the first two well. I'd recommend Eloquent Ruby first, and second either Sinatra: Up And Running or Practical Object Oriented Design, if you want a pragmatic second book. Of course, you could go with Understanding Computation second if you prefer to go down a quirkier rabbit hole; there's no real need to read something else between Eloquent Ruby and this other than perhaps getting used to well-formed Ruby code that does things that can be useful to you in "real life".
Actually, Understanding Computation might even be used as a first Ruby book, if you're really inclined toward this subject matter. Have fun.
I think it makes a great third Ruby book to read; choose the first two well. I'd recommend Eloquent Ruby first, and second either Sinatra: Up And Running or Practical Object Oriented Design, if you want a pragmatic second book. Of course, you could go with Understanding Computation second if you prefer to go down a quirkier rabbit hole; there's no real need to read something else between Eloquent Ruby and this other than perhaps getting used to well-formed Ruby code that does things that can be useful to you in "real life".
Actually, Understanding Computation might even be used as a first Ruby book, if you're really inclined toward this subject matter. Have fun.
August 28, 2017
Good over of things like FSMs, Turing machines, what it means to be Turing complete, and the limits of computability. I'm not a Ruby guru by any stretch, but his code examples are clear and readable for anyone that can follow basic modern OO code in a language like Ruby. It was fun to see the theory expressed as code and general reasoning instead of formal proofs.
I didn't have any "whoa, amazing" responses to what was presented --- most CS practitioners will encounter this stuff as part of their formal schooling. But if you've come to computation and programming from another field, or through something like a programming bootcamp, this is worth a read.
I didn't have any "whoa, amazing" responses to what was presented --- most CS practitioners will encounter this stuff as part of their formal schooling. But if you've come to computation and programming from another field, or through something like a programming bootcamp, this is worth a read.
March 18, 2020
Good intro to the basics
A good introduction to the basics. Machines and programs. Definition of computability. Finite state machines, deterministic and non-deterministic. All the way up to different ways of specifying semantics. BUT I found the overly long overly intricate examples in Ruby hard to follow and something of a distraction.
Short and pithy would have been better. Worth a read though.
A good introduction to the basics. Machines and programs. Definition of computability. Finite state machines, deterministic and non-deterministic. All the way up to different ways of specifying semantics. BUT I found the overly long overly intricate examples in Ruby hard to follow and something of a distraction.
Short and pithy would have been better. Worth a read though.
February 14, 2021
Loved it! Grad school was a very long time ago, and I’ve forgotten a lot of the academic concepts that interested me in computer science to begin with. Reading this book made me positively giddy in spots. Each chapter builds on the previous, and all of them ultimately lead to an investigation into what computation really is, where it shows up, and what it’s fundamental limits are. The author strikes a perfect balance between academic rigor and real-world accessibility. Heartily recommended.
January 28, 2018
This is a highly approachable introduction to computability. It has an exceptionally practical approach, guiding the reader through its various topics using simple ruby code. Even if you've never written ruby (or simply don't like it), do not dismiss the book for its choice of language.
May 10, 2017
A fun review of the stuff I learned in CS252 ("## - new life!"). Clever work here alongside the ruminations on computing power.
March 13, 2022
I only wish this book had a bit more math and chapters on algorithms and complexity theory.
June 19, 2024
An accessible, hands-on introduction to concepts of computing with example code in Python.
August 14, 2014
This book does what it promises to do - take the reader from the most basic simplifications of computers (finite automata), through more complex simplifications (Turing machines) to reasoning about 'impossible' problems (The quotation marks are added because these problems will surely be solved one day or another by some clever fellow with too much brain activity and spare time, but are impossible for now). I really enjoyed the fact that the author was able to use Ruby code to illuminate his examples, which (me being a programmer) made them much easier to understand (easer being the operative word, this s*** is still complex as balls) than the mathematical notation commonly used by textbooks.
However, I feel that Mr. Stuart (much like all other authors of complicated, technical books I've read) falls into the trap of following a very predefined path for his line of reasoning, which leaves the reader with the feeling (at least, this was the case for me) that this is 'all planned out' and that there's a lot of information he intentionally leaves out or doesn't mention (this might not even be the case, but it still FEELS like this - which is a problem). If you have no idea what I'm talking about, read the book, and if you still don't know what I'm talking about then feel free to shake your head condescendingly.
Now, my interest in this particular field of computer science is cursory at best, which might not make me the ideal fit for Mr. Stuart's target audience, so if you get a major hard-on when syntax trees are generated (seek help) then you might get more out of this book than me.
That being said, he managed to peak my interest in concepts I felt were mind-numbingly boring in university (such as non-deterministic and deterministic finite automata), so kudos to Mr. Stuart for that. This book is a possible gold mine for the more interested pupil, especially when considering the problem of Turing completeness (in which he completely lost me, mid-chapter I put the book down and went to the fridge and rewarded myself with a beer for my efforts), reasoning about programs and (wait for it) generation of syntax trees.
All in all a good read, if you're into this sort of thing.
However, I feel that Mr. Stuart (much like all other authors of complicated, technical books I've read) falls into the trap of following a very predefined path for his line of reasoning, which leaves the reader with the feeling (at least, this was the case for me) that this is 'all planned out' and that there's a lot of information he intentionally leaves out or doesn't mention (this might not even be the case, but it still FEELS like this - which is a problem). If you have no idea what I'm talking about, read the book, and if you still don't know what I'm talking about then feel free to shake your head condescendingly.
Now, my interest in this particular field of computer science is cursory at best, which might not make me the ideal fit for Mr. Stuart's target audience, so if you get a major hard-on when syntax trees are generated (seek help) then you might get more out of this book than me.
That being said, he managed to peak my interest in concepts I felt were mind-numbingly boring in university (such as non-deterministic and deterministic finite automata), so kudos to Mr. Stuart for that. This book is a possible gold mine for the more interested pupil, especially when considering the problem of Turing completeness (in which he completely lost me, mid-chapter I put the book down and went to the fridge and rewarded myself with a beer for my efforts), reasoning about programs and (wait for it) generation of syntax trees.
All in all a good read, if you're into this sort of thing.
March 25, 2021
Understanding Computation provides a high-level overview of the theory behind computation. It does so from a highly practical perspective, showing the theoretical concepts using implementations in Ruby.
I used this book as a refresher on the relevant courses during my bachelor. Specifically, I was looking for ways how use the concepts in my work.
Although I had my doubts before reading, the book actually does a great job of covering most of the subjects. The focus on the practical/technical side of things, provides some nice insights that are often overlooked when purely discussing these concepts in theory. In comparison to most books on this subject the book just is a fun, casual read, even when you already familiar with most of the content. I especially liked the section on lambda calculus.
In some cases the author skips over subjects a bit fast, and keeps the description to high-level. His almost zealous attempts to refrain from using any mathematical equations/symbols, sometimes does't work out that well. Same goes for the Ruby implementations; often useful, but sometimes unnecessary or just too verbose.
All in all, great read for anyone wanting to get an introduction or quick refresher about computation (theory)
I used this book as a refresher on the relevant courses during my bachelor. Specifically, I was looking for ways how use the concepts in my work.
Although I had my doubts before reading, the book actually does a great job of covering most of the subjects. The focus on the practical/technical side of things, provides some nice insights that are often overlooked when purely discussing these concepts in theory. In comparison to most books on this subject the book just is a fun, casual read, even when you already familiar with most of the content. I especially liked the section on lambda calculus.
In some cases the author skips over subjects a bit fast, and keeps the description to high-level. His almost zealous attempts to refrain from using any mathematical equations/symbols, sometimes does't work out that well. Same goes for the Ruby implementations; often useful, but sometimes unnecessary or just too verbose.
All in all, great read for anyone wanting to get an introduction or quick refresher about computation (theory)
April 16, 2017
This book is a little pearl. It aims right at the central topic on what is needed and not needed
to perform computation. It covers important material from operational semantics, automaton
theory, different computational models like the turing machine, lambda calculus, partical recusive functions etc. until it closes with important results of in those fields that affect the decidability of problems and ultimately the reasoning about program behaviour. It provides a practical view on that matter by providing example implementations in ruby code. It is truly a marvellous little book, that should not be missing in the bookshelf of an engineer.
The reason why it's only 4 and not 5 stars is because I would have loved to also have the mathematical notation instead of just the ruby code. Nevertheless I can wholeheartedly recommend that book.
to perform computation. It covers important material from operational semantics, automaton
theory, different computational models like the turing machine, lambda calculus, partical recusive functions etc. until it closes with important results of in those fields that affect the decidability of problems and ultimately the reasoning about program behaviour. It provides a practical view on that matter by providing example implementations in ruby code. It is truly a marvellous little book, that should not be missing in the bookshelf of an engineer.
The reason why it's only 4 and not 5 stars is because I would have loved to also have the mathematical notation instead of just the ruby code. Nevertheless I can wholeheartedly recommend that book.
December 2, 2014
Автор використовує Рубі, і пояснює, як створити власну метамову. Суть в тому, щоби на основі цієї штучної мови написати свій компілятор, який би запускав самописні процедури для ядра. Паралельно описується формальна семантика, функціональне програмування і нудна теорія автоматів. Купа коду, читати у форматі електронної книги, як я це робив, просто нема сенсу. Глибока і класна книжка, тільки чого ж бляха Рубі! Очі вилазять, тому що ця метамова на основі Рубі, чим далі абстракції (далі, ніж прості оператори додавання\множення..) стає просто неповоротким і потворним кнуром. Пітон був би вдалішим зручнішим вибором.
November 19, 2015
It's an interesting book about the notion of computation, algorithms, abstract machines, and programs. Especially useful if you've had practical experience in programming and interested in more theoretical ideas behind it. Still, the book uses Ruby to explain the ideas instead of pure math.
It obviously describes the Turing machines and lambda calculus, and also partial recursive functions, SKI combinator calculus, Jota, tag systems, cyclic tag systems, Conway's Game of Life, Rule 110, and Wolfram's 2,3 Turing Machine. Turns out all of them are equivalent, universal, and are able to execute any algorithm. Fascinating!
It obviously describes the Turing machines and lambda calculus, and also partial recursive functions, SKI combinator calculus, Jota, tag systems, cyclic tag systems, Conway's Game of Life, Rule 110, and Wolfram's 2,3 Turing Machine. Turns out all of them are equivalent, universal, and are able to execute any algorithm. Fascinating!
September 3, 2015
First this is not a book about software engineering or programming. Instead it delves into the abstract core of what is the essence of a computer. Concepts like finite automata and Turing machines are a few that are presented and discussed. An engineering or mathematical background is not a requirement to tackling the material. In addition the simulations of the concepts presented are done in Ruby but fear not the author devotes a fair amount of pages to the features of Ruby so the non-programmer can understand the source code in the book.
December 8, 2015
An interesting but brief look at the world of theoretical computer science. Combines an informal presentation with a focus on the practical implications of the concepts presented (e.g. specific examples of problems solvable by DFAs, DPDAs, etc.; automated checking of programs in spite of results like Rice's theorem). Worth the short read but for those interested in a more in-depth discussion of these topics, I recommend a textbook like Sipser's.
January 6, 2014
"Since every Ruby program has a unique number, we can automatically generate all possible programs: start by generating program number 1, then generate program number 2, and so on.5 If we did this for long enough, we’d eventually generate the next hot asynchronous web development framework and retire to a life of leisure." :)
This entire review has been hidden because of spoilers.
December 28, 2023
This is, simply, one of the best computer science books I've read in my career and CS education thus far.
There's so much more to what I want to say about this book, that I can't do it justice here (was thinking of doing a video review of this one). If you're interested in Computer Science, **just read it** (like, drop whatever you're doing and read it).
There's so much more to what I want to say about this book, that I can't do it justice here (was thinking of doing a video review of this one). If you're interested in Computer Science, **just read it** (like, drop whatever you're doing and read it).
July 20, 2013
Good stuff, but not for me at this time. Maybe when I need a refresher.
July 22, 2013
Fun read, inspired me to try out many different toy programming ideas. I skipped over the Ruby examples because the material made sense to me without it.
December 4, 2014
Interesting idea, but the book is rather boring with the code and tech details.
September 4, 2016
loved it, one of the best
July 21, 2018
4.5
đã học được món automata T_T
đã học được món automata T_T
Displaying 1 - 29 of 29 reviews