Computers Ltd.: What They Really Can't Do
Book written by David Harel
Book review by Pablo Breuer
Bottom Line: I recommend this book for the Cybersecurity Hall of Fame.
Every tough university major has that one “weeding out” class that every student dreads. Those classes are full of arcane knowledge and it’s not always clear why they are required in our chosen profession.
For computer scientists, that class is automata theory - a branch of linear mathematics that analyzes various computing machines and the problems that can be solved by them. Many of us survive the course without giving it much thought until much later in our careers.
What we miss is that automata teaches how to answer every hard technical question we’ll have in our computing career whether we’re discussing coding, information security, artificial intelligence, or whatever the next technical innovation will be. Computers Ltd. manages to impart this knowledge without having to relearn our Greek alphabet to conduct proofs. It is an invaluable resource for researchers, practitioners, and decision makers.
What is Automata?
Automata is the theory of computers and computation. It uses mathematical notation to describe computing models, languages, the problems that they can help us solve, and, more importantly, the problems they can’t help us solve. Often, problems of interest require more powerful processors, greater amounts of memory, or larger/faster storage.
There are some problems, however, that can never be solved with computers. The issue with these problems is that many of them sound deceptively simple. We are surrounded by problems that sound easy enough but hide tremendous complexities. Sometimes these complexities can be overcome by brute computing strength, but some are so insidious that if every atom in the known universe were a supercomputer, the sun would still burn out before we arrived at an answer.
Automata helps us analyze problems of interest and decide if they’re something that will be relatively easy for a computer to solve, difficult for a computer to solve, or if they’re of the impossible kind of problems to solve. More than that, automata provides a way to conduct various proofs so that we can be mathematically certain of our answer.
Why is Automata Useful?
For the researcher and the coder, automata allows us to know when we are chasing down the wrong question, when our sample size is too large, and when we may have to live with an answer that is not exact. This is useful, but it is not what many of us do once we graduate. So why is it taught?
Have you ever looked at a software or hardware product page making amazing claims? Has your boss ever asked you to evaluate the security claims of two competing products? Have you ever ridden the rollercoaster of the Gartner Hype Cycle after being inundated with the industry’s buzzwords after an industry event?
If you have, “Computers Ltd.” is here to help. By removing the confusing math notation and explaining the principles, automata allows practitioners and managers alike the ability to evaluate problems, compare and contrast products, evaluate vendor claims, and hack the “sales-speak” to arrive at a greater understanding of what you will and won’t get with solutions you’re considering.
Teaching Math Without Math
The author does a fantastic job of walking the reader through a series of automata concepts. There is a basic description of algorithms and programming to set a baseline for the conversation. What follows is a series of discussions around easy-to-follow problems that demonstrate basic automata language and theory. To be fair, this is not light reading. The book is a very dense 200 pages and it will be slow and thoughtful reading.
The discussions begin with what cannot be done via the use of The Halting Problem. Once decidability is explored, the reader is carefully led through a discussion of examples of P, NP, and NP complete problems. These discussions are well organized, easy to understand, and thought provoking if the material is new. The book finishes up by examining how we “solve” problems that are unsolvable and presents a few thoughts on what the future may hold.
Anyone who works in technology will say that technology moves fast. Every year, we are inundated with new buzzwords in the security industry and left to figure out if these new technologies will finally solve our greatest challenges.
While it’s true that technology moves quickly, the theoretical underpinnings covered by this book have not fundamentally changed since the time of Alan Turing, and that is what makes this book both valuable and rewarding. By educating ourselves on the fundamental precepts, we can better understand our challenges, move beyond the false sales promises, and move to substantive conversations. This is dense reading, but for those that are willing to invest the time to understand this book, the rewards are innumerable.