| Understanding Computation |
|
Author: Tom Stuart
What exactly is computation? In many ways it is important to know what this book is not about. The clue to the subject matter is contained in the subtitle: From Simple Machines to Impossible Programs. If you know some computer science then you will guess that this is about the hierarchy of theoretical computational machines and things like the halting problem. Of course, if you don't know any computer science you won't have the slightest idea what this book contains - subtitle or no. It is slightly easier to explain what the book is not about. Do not buy this book if you want to learn how to program or learn about practical aspects of programming. It also isn't about number crunching, aka numerical computation. What is is about can't really make much sense unless you read the book or already understand some of the ideas. This is a book about the theory of computation and the sorts of machines needed to do particular types of task. This is usually called "theoretical computer science", but this isn't a typical computer science book. Once you know what the book is about you also need to know that it makes extensive use of Ruby. If Ruby isn't a language you like, or if you can't be bothered learn Ruby, then you are going to miss out on a lot, but not all, of the book's value.
The first chapter introduces Ruby at a level that you can use to pick up the language if you are already a programmer. If you are not a programmer then this is almost certainly not the book for you. It is a lightening introduction to Ruby in that it is all of 13 pages long - as its title says "Just Enough Ruby". The reason for the practical introduction to Ruby is that in the rest of the book Ruby is used to implement examples of what are often just theoretical constructs. If you are happy to have ideas explained as just theory then you might well object to the amount of Ruby needed to create programs that do something that you probably don't really want to do. In Chapter 2 things do look a bit more practical as the subject is code semantics. This starts off with a look at abstract syntax trees (ASTs) and small step semantics. In this case seeing the code that implements and evaluates the AST is enough to convince you that you could write a compiler. Next we learn about big step semantics and again the practical presentation as Ruby code helps understanding and confidence. What is missing is a look at the details of syntax analysis which is handed off to a Ruby utility. This is a bit of a shame as grammar and parsing is worth a deeper look. At the end of this chapter you will have some idea what language implementation is about and appreciate some of the theory of language semantics. Chapter 3 starts a set of chapters that examine the hierarchy of machines that move from the simple to the more complex. The surprise for the reader is that some simple machines can do more than you might expect, although not everything, but when you try to extend them by apparently making them more powerful this sometimes doesn't work. It is an investigation of what really makes one computing machine more powerful than another. We start off looking at deterministic finite state machines and discover that there are some things they cannot do. Then we look at non-deterministic finite state machines and discover that while they look more powerful, they aren't. Next. in Chapter 4 we move on to Pushdown Automata, or stack-based machines and find that these are more powerful and in this case non-deterministic pushdown automata are even more powerful. Finally in Chapter 5 we meet the most powerful machine - the Turing machine. It is the central tenet or dogma of computer science that anything that can be computed can be computed by a Turing machine, i.e there are no more powerful machines. Of course, you can build machines that are faster and more efficient than a Turing machine, but this isn't an argument about practical computing but rather what can be computed in theory if you have enough time and resources. In these chapters the use of Ruby to actually write implementations of the machines in question seemed less useful to me. I think that most readers would grasp the way a finite state machine worked without the level of detail provided. It is a great way to learn some Ruby, but it could well be regarded as getting in the way of learning the theory. Which you think is the case depends very much on your learning style. One thing that wasn't explained well enough was the connection between machine power and languages. The Chomsky hierarchy isn't mentioned or if it is I didn't notice and that's not enough emphasis - it's a missed opportunity.
Now that we have the Turing machine we can investigate what is and what is not computable. This is what Part II of the book is about and Chapter 6 introduces the idea of the lambda calculus, and again uses Ruby to implement it. Chapter 7 explores the idea of universality - i.e. that most complex systems are equivalent to a Turing machine and can compute anything it can. In this chapter we learn that lambda calculus is Turing complete and so are lots of other similar computational systems including Conway's Life and some cellular automata. Chapters 8 and 9 bring the book to a close with an explanation of what cannot be computed and how to react to this idea. These final chapters are a strange mix of the halting problem and Godel's theorem. You will also find some musings on why all this is important in one sense but perhaps not practically.
This is a fascinating book and if you think that a practical introduction to many aspects of computer science is something you would appreciate then it comes highly recommended. I need to warn readers who are not willing to spend the time doing the practical side of things that this isn't the most straightforward way to tackle the ideas. There is a tendency to get lost in the practicalities of Ruby. It also isn't the most logically organized approach to the subject and it certainly doesn't follow a textbook approach. The chapters to hang together to tell a story but it isn't a complete story in any sense - you won't find out about complexity classes, for example, so no P and NP. Overall this is a book I enjoyed reading and, as long as you can accept the book's omissions and defects, you might do the same. Recommended but with many conditionals. For more recommendations of Ruby related titles see
|
|||
| Last Updated ( Friday, 22 December 2017 ) |
