The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine

by Charles Petzold

Programming Legend Charles Petzold unlocks the secrets of the extraordinary and prescient 1936 paper by Alan M. Turing Mathematician Alan Turing invented an imaginary computer known as the Turing Machine; in an age before computers, he explored the concept of what it meant to be computable , creating the field of computability theory in the process, a foundation of present-day computer programming. The book expands Turing’s original 36-page paper with additional background chapters and extensive annotations; the author elaborates on and clarifies many of Turing’s statements, making the original difficult-to-read document accessible to present day programmers, computer science majors, math geeks, and others. Interwoven into the narrative are the highlights of Turing’s own his years at Cambridge and Princeton, his secret work in cryptanalysis during World War II, his involvement in seminal computer projects, his speculations about artificial intelligence, his arrest and prosecution for the crime of "gross indecency," and his early death by apparent suicide at the age of 41.

Genres: Computer Science, Science, Nonfiction, Programming, Mathematics, History, Technology

862 pages, Kindle Edition

First published June 16, 2008

About the author

Charles Petzold has been writing about programming for Windows-based operating systems for 24 years. A Microsoft MVP for Client Application Development and a Windows Pioneer Award winner, Petzold is author of the classic Programming Windows, currently in its sixth edition and one of the best-known programming books of all time; the widely acclaimed Code: The Hidden Language of Computer Hardware and Software; and more than a dozen other books.

Reviews

[Mark Seemann · Rating 5 out of 5]

This book reprints Alan Turing's 1936 scientific paper On Computable Numbers, with an Application to the Entscheidungsproblem, with 'a bit' of commentary.

The paper is 36 pages, so the remaining 300+ pages are Charles Petzold's explanation of the paper. The book starts with explaining the (mathematical) context of the paper: what had come before, which problem it addressed, and some important mathematical tools and results required to understand the paper.

The paper itself is terse and dense, so even armed with Petzold's explanation of the context, I'd been unable to follow it had he just dumped it verbatim. What he does, instead, is that he cuts it into small fragments, and then he takes the pages required to explain what happens in Turing's text. He does a tremendous job of that. Every time I felt that I didn't understand a particular definition or formula, Petzold's notes comes to the rescue.

Armed with my 20+ year old, passive maths knowledge, I was able to follow most of Turing's paper. It probably helps that I'm a professional programmer, so I found the description of computing machines tractable, although I had to pay close attention and work through some of the pages more than once.

This is possibly the most spellbinding hard-to-read book I've ever read. The book is hard to read in the sense that it required all my attention to follow, but it was just at the right level for me, and I enjoyed it throughout.

[Deirdre · Rating 5 out of 5]

Wouldn't you like to know the outcome of your actions before you decide what to do? Looking into the future, you could see if biting that apple was a good idea or something completely different and unexpected.

However, there's no way through it but to do it.

Well mathematicians and computer programmers have the same problem. British mathematician, Alan Turing, proved that there is no way a computer can be designed with the correct set of instructions (program) so as to be able to determine if any other program will work properly. The program in question must be run -- come what may.

By proving that to be true, he also proved that there was no set of instructions or number of actions that could analyze a mathematical formula and see if it's going to work (or be decidable) except doing the math.

It sounds simple, and my husband Charles Petzold almost makes it seem simple in his new book The Annotated Turing: A Guided Tour through Alan Turing's Historic Paper of Computability and the Turing Machine.

You like that sly disclosure? Here is another one. I haven't ever read a mathematical paper. I haven't thought much about math since I took my last class in it in 1977. Although I did receive a Math/Science Regent's Diploma from Clinton Central School in 1978, I did so without taking either subject my senior year.

Did I understand Charles' book? Yes. I read it carefully and I think I got the first eleven chapters. Please don't quiz me, but I seemed to follow the basic idea. I tried to ask him few questions as I read. I will admit that I've been listening to him talk about the book for the last nine years though. I will admit to being overwhelmed in the chapters on mathematical logic. They were words and numbers on a page.

However, if anyone out there is a computer programmer or a math whiz, take a look at the book. Alan Turing's paper, "On Computable Numbers, with an Application to the Entscheidungsproblem," was historic for many reasons. He solved one of Hilbert's famous problems. He imagined a machine that could do what all computers do these days. And he showed the limitations of computers and software before they existed.

Charles is a great guide in this endeavor. Impress your professors, read it this summer and dazzle them this fall.

--

[Nick Black · Rating 3 out of 5]

Amazon 2008-10-24. This book needed to decide earlier on whether it was going to be pop-CS or a real book. There's some great insights here -- I finally feel that I truly know the difference now, in a deep sense, of what makes a given transcendental number computable or not (there's unfortunately rather little detail on computable functions themselves, but that's an easy extension from computable numbers). Kudos to Petzold for his fine background material on Hilbert's erweiterte Funktionenkalkul, unentscheidbare Satze, and the Entscheidungsproblem and absolutely excellent bibliography -- there's a surprising number of histories of computing and logic that I'd never heard of, despite considering myself pretty well informed on such topics (Petzold seems incredibly well-read in the works of Chaitin and Davis, for one). Unfortunately, a good chunk of said references are to Oxford- or Elsevier-published collected works, meaning they're sure to be hundreds of dollars each, bah. There's also two great, great quotes I'd never heard before:

Bertrand Russell, upon hearing of the RAND Corporation's "Logic Theory Machine" and Hon Wang's IBM 704's work in automated theorem proving:

"I am delighted to know that ' Principia Mathematica' can now be done by machinery. I wish Whitehead and I had known of the possibility before we wasted 10 years doing it by hand."

and, even better, from the inimitable Johnny Von Neumann:

"I've not read a mathematical paper since Godel."

LOL! Therein end my praises for The Annotated Turing. The paper of Turing itself is shockingly weak, replete with trivial lemmas and hardcore errors in his central construction, setting the tone for half a century of busted machine proofs, bugs, failures and errors. As Maurice Wilkes said:

As soon as we started programming, we found out to our surprise that it wasn't as easy to get programs right as we had thought. Debugging had to be discovered. I can remember the exact instant when I realized that a large part of my life from then on was going to be spent in finding mistakes in my own programs."

Or, to quote myself in CS6262 earlier this semester:

"Basically, the Safety Problem tells us that reasoning about combinatorial automata is difficult."

Do we really need another 60 pages wasted on introductions to basic set theory and first-order predicate calculus? Is there really anyone (useful) on Earth who doesn't have these two abstractions burnt deep in their brain yet? Also, Petzold shies away from proving his own assertions, even when the trivial mechanisms to do so are used later on in his own book!

I'm glad I read this, but I won't be reading it again. I will, however, be reading a good bit of the bibliography. Science, ahoy!

[Shital · Rating 5 out of 5]

It was about 10 years ago when I first found Turing's original paper on Internet and thought it wouldn't be so hard to read and understand it (after all its "mere" computer science). Since then I've tried to digest it quite a few times on and off and never actually succeeded. Infect most of the time I got stuck on few nitty-gritty and just couldn't move forward. I have even bought/borrowed almost all books on the subject that falls in to "popular science" types. Needless to say, like many such books in same category, they just never go in to details and are practically useless for all practical purposes :).

So imagine my surprise when I see a book with title "Annotated Turing" and by none other than Charles Petzold who I've known as author who normally writes programming books. That surprise was only a start. I was simply shocked when I opened the book. It was as-if someone read your dream and made it a reality with absolute precision with zero compromises. If there is one such book like this for all of the milestone scientific papers, there would be a revolution in learning.

Let me put out some points what makes this book so perfect. Not just wishy-washy "near perfect", I'm saying SO PERFECT.
*First, the book contains explanation of every single line in Turing's paper. Literally. The format of the book is a line quoted from Turing's paper in bold and a paragraph or so of explanation and discussions for that line. Author's claim is that you can actually cut out all those lines and stitch them to recreate the Turing's paper in its entirety complete with page numbers! Now that's what I call precision.
*The book also includes all encompassing big picture overview, historical situation, importance, consequences and so on - nicely preparing reader for the journey.
*The book is so readable that I usually forget I'm reading a very technical book that goes in to very core of computer science. It's like nicest computer science professor reads you the paper line by line and answers all your questions, even those completely stupid ones.
*As I'd doubted many times, there are lots of errors in Turning original paper. This book amazingly points them out and corrects even the minor misprints. I'm just surprised how author even know so much "insider" details about those trivial misprints and errors.
*Turing's paper is full of obscure strange symbols (have you seen old gothic German font?) that are common in scientific literature today. Author explains all these symbols, what they mean, where they came from, what are the subtle differences and so on. Just amazing.
*Turing's paper have lot of omissions for explanations and steps which he probably left out as "exercise for reader" to keep his paper short. Sometime you might get stuck in those exercises and if you are not in academia you probably have no external help. This book deals with all these omissions and expands so beautifully on them that I can't imagine if there any better way to describe them.
*Apart from omissions, there are lot of shortcuts that Turing employs with rather flitting explanations or sometime absolutely none. This book covers you 100% for these shortcuts.
*A big part of understanding Turing's paper is actually mentally running his machine's step by step for all the examples he puts out. This book actually does this step-by-step run explanation making it so easier to read and understand quickly.

Anyway, some of you might think why one should even bother about reading this ancient computer science paper in first place? Answer is huge changes in the way we have started viewing universe recently. While Seth Lloyd's book "Programming the Universe" does good job of explaining this thinking, the summary is that the universe can be seen as computing machine rather than particle and energies in the realms of physics. There was even a paper that proposed that even a simple system consisting of billiard balls interacting in space is Turing complete! That means by setting billiards balls in some initial points in space and velocity can computer anything that your laptop can compute in theory. To understand advances in this area you have to fully understand what is Turing's machine and what it means to be Turing complete and how one can prove that a certain system is computationally Turing complete. That's where the paper comes in. Text books just don't do justice.

[Erkin Unlu · Rating 5 out of 5]

Bu kitapla İTÜ Bilgisayar yıllarıma geri döndüm : ). Döndüm dönmesine ama koskoca 4 yılda Turing makinalarını öğrendiğim zamanı hatırlayamadım. Biçimsel Diller ve Otomatlar dersinde öğrenmiş olmam gerektiğini biliyordum ama hatırlayamadım. Ulan yoksa İTÜ’de Turing mi öğretmiyorlar derken sebebini biraz araştırma yaparak farkettim: söz konusu ders Turing makinalarını en sona bırakmıştı. Son haftaların konuları da genelde finallerde çıkmadığından, o kısımlara ya çalışmamışım ya da hiç öğrenmemişim. : )) Zar zor geçmiştim zaten o dersten.

Kitabı kesinlikle her bilgisayar mühendisine ve matematikçiye öneririm. Bilgisayar ve matematik bilimi açısından çok büyük önem taşıyan Çözülebilirlik, Sonsuz Kümelerin Sayılması, Gerçek Sayıların Sayılamaması, Devam/Dur problemleri gibi konuları anlaşılabilir dille anlatmış yazar(çünkü Turing anlaşılabilir biçimde anlatmamış:) ). Turing’in hayatını(kısa ömründeki başarıları ve kendisini intihara sürükleyen süreç) ve çağdaşları olan önemli bilim insanlarının hayatını anlatması açısından da oldukça önemli bir çalışma olmuş.

Kitabın özellikle son bölümü ayrıca bilgisayarlar, zihin ve limitler üzerine felsefi yaklaşmak isteyenleri de tatmin edecektir. 5 yıldızı bir bilgisayarcı olarak veriyorum, konusu matematik yada bilgisayar olmayanlar bu değerlendirmeye bakmasınlar : ).

Not: Kitap yer yer zorlaşıyor(özellikle az sayıda da olsa Turing’in hatalı yazdığı tasarladığı kısımlar var), ve zor kısımları anlamak oldukça güç. İşaretleyip, kitabı bitirdikten sonra dönmek daha faydalı olacaktır.

[Ruthie · Rating 5 out of 5]

I will genuinely miss staring at Turing’s equations every evening. I will definitely miss the eureka moment when (often with Charles Petzold’s help) they finally arrange themselves.
It’s a really cool opportunity to read a real academic paper, especially one as incredibly insightful as Turing’s, and have it explained to you step by step.
What I found most incredible reading it was that Turing’s work was written before the computer - and yet he introduces hypothetical machines which can perform the same operations our computers can today.
I would definitely recommend, even just for the joy of learning a little more about number theory - it never bores you!

[Stuart · Rating 5 out of 5]

This is one of those books that is so deep that I doubt anyone can read it cover to cover without having to go back and puzzle over the contents of some of the chapters. It is intended as a commentary on Turing's paper which, in some ways, due to the notation Turing uses, is more difficult to understand than it needs to be. Petzold plows through this giving several lines of commentary and examples to each line of Turing's paper.

Petzold demonstrates his knowledge of computing and mathematics and has obviously read and understood the mathematical papers that form the backdrop and purpose of Turing's paper and he refers to them knowledgeably.

No book on Turing can avoid the tragic story of his short life and Petzold covers this in a sensitive way intertwining both the depth of the mathematical theory and historical background in a seamless way.

I'm reminded of Bill Gates review of Knuth's work: "If you think you're a really good programmer . . . read (Knuth's) Art of Computer Programming . . . You should definitely send me a résumé if you can read the whole thing.". This book is, along with Godel, Escher, Bach in the same category.

This book is of the level of advanced Computer Science Degree and should define Petzold's legacy more than all of the seminal Windows programming books that he has written over the last 20 years.

[Mosaad Al Thokair · Rating 4 out of 5]

أن تكون قادر على استشفاف كمية هائلة من المعرفة تقود اكتشافات قرن قادم، بمعرفة يقينية لا يشوبها شكوك تجربة ولا تشوهات واقع.
أن تكون قادر على رسم حدود مايمكن ومالايمكن بآلات أوجدتها داخل عقلك.
أن تنير جزء من العالم المظلم الذي نعيش فيه بلا أن تقوم من مقامك.
أن تكون رياضيا.
"Math is pure and perfect, science is impure and imperfect"

[Hemanth Kumar · Rating 4 out of 5]

By far the comprehensive explanation on Turing machines. It is a interesting text but it is a text nevertheless.

[Bram · Rating 5 out of 5]

I found this book to be the most enjoyable way to read a scientific paper ever. The way the book is structured is just excellent: Historical context provided but optional, scary maths not simplified but explained and also optional. On top of that, the writing is very accessible and nice to read.

The only problem I had in reading this was not so much to do with Petzold (or Turing) but with the logical syntax and the way it is presented. There is such a sheer amount of symbols in this paper that even to someone used to the syntax, the formulas towards the end of the paper become borderline unreadable without a legend. The finishing touch to this book would be to provide some sort of system that would make this more "reading-material" than "study-material".

Nevertheless, this was an exellent book and I think this kind of text is how fundamental research should be presented much more often.

[Zach · Rating 3 out of 5]

Very useful for making it through Turing's famous (and dense) paper. Petzold sets the context for the paper and draws out its implications for thought. Turing invented the Turing machine on his way to showing that there is no general decision procedure for determining the logical validity of a statement. You may not care about all the math needed to get to this point, but it's there if you want it.

[F Avery · Rating 5 out of 5]

If you have any interest in computers, mathematics, the limits of logic, or the history of science and mathematics, this is a marvelous read. I personally would put it in the top five books I've ever read.
That said, it's not an easy read. I have graduate degrees in mathematics, and have worked with computers for nearly 40 years, and still found parts of it challenging.
As there are already many reviews describing the kind of book this is, I won't go into detail, but will just list some parts that I found particularly interesting.
In the introduction the author gives an outline of the book and what you can skip if not interested. And I was happy to find this sentence on page 149: "No one will punish you if you don't assimilate every symbol and function in Turing's description.". However, the background material on the real numbers and the concept of enumerability are essential to understanding the importance of Turing's proofs. I personally think it's worth the time and effort to at least skim every section.
I also loved the occasional esoteric humor. For example, on page 21 under a diagram of the real numbers is this infinitely understated sentence: "This diagram is not to scale.". You'll get the humor once you've read and understood the concepts of enumerability and Cantor's arguments about the real number line.
I particularly enjoyed Chapter 16 Conceiving the Continuum, with its discussion of controversy in mathematics. I hadn't considered the fact that Cantor's and Turing's proofs imply that there are real numbers that are not computable by any algorithm, i.e. they are completely inaccessible to us. In what sense can one say such numbers exist then?
In conclusion, it's an engaging and educating read. The time and effort to read it are well spent. But if you have no interest in the subjects mentioned in my opening paragraph, this is probably not the book for you.

[Nathan Ormond · Rating 5 out of 5]

A very good book on mathematics, computation and philosophy of mind

[Dylan Lea · Rating 5 out of 5]

Actually enjoyable nonfiction

[Jeroen Vaelen · Rating 2 out of 5]

That was a struggle

[Eduardo Rodríguez · Rating 4 out of 5]

A book I would recommend to anybody that has studied Computer Science or Mathematics. However, the last section is too heavy on Propositional logic and I would personally recommend skipping over it unless you know what Formalism is and you enjoy mental pain.

Thanks Mr. Petzold, for bringing us such an easy to read description of what Turing once posed on paper. I believe there is a cloud of uncertainty and mysticism on what Turing once did as a mathematician, many computer geeks (such as me) might believe that he simply defined what is known as a Turing machine. But there is much much much more to it, and now I know why he was such an important figure.

This would be a 5 star book to me if I could understand a third of the mathematics behind the paper.

[Jose · Rating 5 out of 5]

Good read

[Mengsen Zhang · Rating 4 out of 5]

Nice book! If you think this book is just an annotated version of Turing's paper on Computable numbers & Entscheidungsproblem, you're probably gonna be frustrated to see a paper of 30-ish pages has been stretched out into over 300 pages. However, it's more like that you traveled back in time to visit Turing and he (and his machine) introduced you to the most beautiful intellectual epics surrounding those decades. The dreams and dramas about numbers haunt human thoughts forever, at least since the Greeks. Discrete or continuous - where mathematics and existential philosophical questions converge. In the background of Turing's paper, it's translated into: the infinity of natural numbers is not the same as the infinity of the continuum (re: Cantor, Transfinite number). A key is that real number is not enumerable. What I found most intriguing is how Turing established the connection between the unenumerability of computable numbers and the decidability problem of predicate logic. What's also amazing is how the "scaffold" set up for building such connection - the imaginary machine - left the greatest impact on every human life ever since. The struggle between the discrete and the continuum seems to generate new "life forms". Well, but that's just my over-imagination.
Overall, Turing first introduced a (finite state) machine that reads and writes on a paper tape to calculate numbers. In certain sense, each healthy Turing machine represents a number with infinite digits (a healthy Turing machine prints forever), while the description of a machine (states and methods) can also be represented by a finite number. So you end up with a finite number (sometimes) represent a infinite number. Second, he show there's no general way to decide if a machine ever prints zero. Third, he established a mapping between logical proving and number computing. Then undecidable number problem becomes undecidable predicate logic problem.
In the appendix, he also showed the relationship between his machine and Lambda calculus. Despite how much I like LISP... oh damn, reading that part really made me want to bounce my head on the wall...
Final alert: though I really appreciate the author's effort, sometimes he really turned it into an Annotated Petzold (by Turing), and it's helpful to avoid some of his annotations. But cheers!

[Kam Yung Soh · Rating 4 out of 5]

An impressive book that gives you an annotated guide through Turing's historic paper on computation. It starts with a background in mathematics and number theory, defining various concepts that are required to understand the paper.

Next, the author covers probably the part that most interest me: Turing machines. Turing shows how such machines can be used to perform computation and, in an impressive series of steps, shows how a Universal machine can be used to execute the operations of any Turing machine.

Finally, Turing shows how his Universal machine can be used to prove that, in general, it is impossible to decide whether a Turing machine will ever output a 'True' or 'False', hence there is no solution to the 'Entscheidungsproblem'. This part was hard for me to digest and I'll definitely need to re-read this book to get a better understanding.

In the final part of this book, the author shows Turing's influence on computer science.

This is an interesting book to read even if you just want to know a bit more about mathematics and Alan Turing. But the guide through his paper gives you greater insight into why Turing is considered such a giant in the field of computing.

[Scott Lerch · Rating 4 out of 5]

This book was literally sitting on my nightstand for years. It was intimidating, dense, and extremely steeped in academic mathematical notation. The key to getting through it, for me personally, was to not get bogged down in the details. The historical context, biographical stories, and overall summarization of Turing's paper is excellent and I thoroughly enjoyed those parts. I even kept up with the definition of Turing machines, the notation, the workings, etc. but once the book is knee deep in the definition of a universal Turing machine it gets quite hairy. From there on the logic, math and proofs don't let up but as I said interspersed are fascinating stories and historical context that make it worth the read. They are almost like treats for getting through several pages of table after table filled with seemingly random Greek, German and English script. I guess what I'm trying to say is only a mathematician can fully enjoy this book. I already knew the salient conclusions from my computer science background and for most in my field that's enough. There is nothing new in this book that I can apply to my day job but nonetheless it was a very entertaining read - minus the complicated logic and proofs, obviously.

[John · Rating 5 out of 5]

This book is exactly what it says it is, a very well annotated version of the paper where Alan Turing introduced the machine that bears his name and sketched the limits of computing. The full text of the paper is included, set apart from the explanations and background research by a shaded background. The explanations are detailed and clear. The historical background information is relevant and interesting. In under 400 pages the reader is led to understanding one of the most important academic papers ever written.

[Dale · Rating 5 out of 5]

This is a wonderful book. Petzold does a line by line exegesis of Turing's 1936 paper on computability, explaining the historical and mathematical background, and showing illustrative examples. The book is probably most interesting to computer programmers, but would also be of interest to anyone interested in mathematics or the history of computer technology. Having attempted to read Turing's paper several years ago, I found that this book really closed my gaps in understanding.

[Jef · Rating 4 out of 5]

This book turns Turing's rather terse paper into a great introduction to computable real numbers.

[Jacob Williams · Rating 5 out of 5]

I really admire the extreme attention to detail in this book. Petzold doesn’t gloss over anything: he calls out issues in Turing’s paper from small typos to major errors in formulas; he provides historical context not just on how various thinkers contributed to their fields, but on whether and by which specific books/etc they were likely to have encountered and been influenced by each other.

Turing’s 1936/1937 paper is (relatively) famous for proving that it’s impossible to write a program that takes any arbitrary program as input and determines whether that program ever halts. Though as Petzold explains, this is not exactly how the paper frames the issue—rather, it divides machines (programs, basically) into two groups that Turing calls “circular” and “circle-free” based on their behavior, and shows there cannot be a machine that determines whether any given machine is circular. This is essentially equivalent to the halting problem, but the latter terminology comes from Martin Davis, years later.

Proving the unsolvability of (what would come to be called) the halting problem was just one step in Turing’s paper, not the end goal; the end goal was to prove that Hilbert’s Entscheidungsproblem (decision problem) was unsolvable. Sadly for Turing, Alonzo Church published his own proof (based on his lambda-calculus) that the Entscheidungsproblem was unsolvable before Turing’s paper made it to publication. Which sounds like an academic’s worst nightmare to me, but Turing and Church went on to collaborate and Turing’s paper still went down in history, so I guess it could have been worse.

Here’s my attempt at an overview of Turing’s paper based on my imperfect understanding of the book (I’ve probably got some of this embarrassingly wrong, and I’m definitely speaking very loosely):

- Hilbert hoped there was a procedure you could follow that would tell you, for any statement, whether that statement was provable or not according to the rules of some formal mathematical system. The search for such a procedure was called the Entscheidungsproblem.

- Church and Turing (in their different ways) proved that there is no such procedure. There are some statements which, no matter how long you search for a proof of them, you will not know whether they are unprovable or you merely haven’t stumbled across the proof yet.

- How is this different from Gödel’s famous incompleteness theorems? IIUC, something like this: Gödel proved that not all true statements are provable within a system. Church and Turing proved that you can’t even identify all the provable statements (let alone all the true ones).

- Turing’s basic strategy was: First, he defined a notion of a “machine”, which was designed to support all the operations necessary to carry out any possible algorithm. Then he showed that you can’t make a machine that determines whether a given machine ever reaches certain states (essentially, the halting problem). Finally he showed how a machine and its states can be represented by statements of propositional logic, such that statements representing future states can be logically derived from statements representing the initial configuration. If a decision procedure existed, you could use it to tell whether any given such statement is provable, which would tell you whether the corresponding machine ever reaches the corresponding state. And since machines can implement any algorithm, you could implement this decision procedure as a machine—but that would be a machine which does the very thing that Turing already proved no machine can do. Conclusion: it’s impossible for such a decision procedure to exist.

The book also helped me appreciate the profundity of Turing’s conclusions. The unsolvability of the halting problem and the Entscheidungsproblem may indicate fundamental limits on our ability to make predictions. From a given starting point, there may be no way to know—even in principle—whether some events will ever happen other than to simply wait and see, or to run a full step-by-step simulation:

When Stephen Wolfram began studying the complex structures that arise from cellular automata, he tried to find ways to predict the outcomes and perhaps make shortcuts through the generations. He could not, for “there can be no way to predict how the system will behave except by going through almost as many steps of computation as the evolution of the system itself . . . For many systems no systematic prediction can be done, so that there is no general way to shortcut their process of evolution . . .”[1]

[1] Charles Petzold, The annotated Turing: a guided tour through Alan Turing’s historic paper on computability and the Turing machine (Indianapolis (Ind.): Wiley publ, 2008), 350, quotes from Wolfram’s A New Kind of Science p. 739, 741, 750.

(crosspost)

[William Schram · Rating 5 out of 5]

The Annotated Turing is a book by Charles Petzold. It covers Alan Turing's seminal papers on The Turing Machine and Computability. Petzold discusses Turing's life at some points, too.

The book starts with a background on what Turing's papers addressed. You may know who David Hilbert is from other mathematical ideas. In 1900, Hilbert proposed 23 pressing problems for future mathematicians to solve. The second problem is to prove the consistency of arithmetic axioms. Kurt Gödel proved the answer is unprovable.

Hilbert also proposed a problem called Entscheidungsproblem, or the Decision Problem in English. It asked whether someone could develop an algorithm capable of demonstrating the truth value of any statement. Alonzo Church and Alan Turing both arrived at the same conclusion through different means. The answer is no. Mr. Church used the Lambda Calculus, but Mr. Turing invented a novel concept dubbed a Turing Machine. Turing's solution is more intuitive and understandable. The Turing Machine is a hypothetical computing device capable of calculating anything a computer can.

The Annotated Turing covers Turing's original papers and contains Petzold's comments on the works. I appreciated the comments explaining the different typesets and fonts. For example, I didn't know that the German Gothic lowercase "K" looks like an "F." The German Gothic "S" looks like a "G."

I enjoyed the book. Thanks for reading my review, and see you next time.

[Tim Regan · Rating 5 out of 5]

I feel a bit guilty including this as 'read' because by the end I was definitely skipping chapters.

When I left Microsoft Research I had to take a long hard look at the books on my bookshelf (some read, some not) and decide which to take home and which to bin. This was in the 'take home' pile.

Turings work on computability is so famous, and so often sketched out, that—rather naively—I'd assumed the actual proof would be easy to follow. This book did a great job showing me how wrong I was, even though Petzold does a sterling job clarifying Turings paper.

For me the best bits of this book were the historical bits, where Petzold places Turings work in two contexts: the first is the historical sweep of mathematics and computing, i.e. what lead to Turing's ideas and what did his ideas lead to (including discussion of opposing mathematical schools of thought) and the second is Turing's personal history, i.e. when was he exposed to various ideas, where, and by whom.

So I totally recommend this book even if, like me, you end up skipping bits.

[Michael · Rating 2 out of 5]

There are a couple interesting takeaways from The Annotated Turing: one, that Turing’s original paper, while insightful and difficult to parse, is also replete with errors, making it even harder to decipher; two, even Petzold doesn’t put that much effort into proving his annotated assertions. I have been looking forward to taking the time to read this book for almost nine years. It definitely has some good parts: It explains transcendental numbers, set theory, and notions of infinity in a way that is easily understood, and I enjoyed the historical context behind some of the mathematical discoveries. Unfortunately, I did not feel that elucidated much of Turing’s paper. Petzold phones in a lot of his explanations, with many of them going far over my head; by the end of the book, I didn’t even bother trying to follow along because I was almost completely lost. Many of his annotations are inscrutable to people who don’t already understand the paper. Needless to say, I was sorely disappointed by this book. Petzold may be a great software developer and perhaps even a better computer scientist, but his teaching skills could use refinement.

[Prahesa · Rating 5 out of 5]

Turing devised a totally new framework in order to solve Hilbert's Entscheidungsproblem (decision problem) in a from of what we know today as Turing Machine. This imaginary machine turns out to tell a lot more than to just being used as a solution of Hilbert's problem.

In this book, The Author gives a nice introduction and background history of why Turing's paper is important. He also try to explain in details of what Turing was trying to convey in his paper. At the end of the book, The Author also highlights the importance of Turing's paper in knowing the universe(s) and consciousness.

A good read for anyone curious enough, and a good refresh for Computer Scientists-alike.

[Qiongsi Wu · Rating 4 out of 5]

This is a very nice book on the classical paper by Turing. The annotations are extremely helpful. They offered a ton of interesting background and explanations.

The only reason (very personal reason) that I am not giving it 5 stars is that this is still not a good book as an introduction to Turing machine (which was what I bought it for). I was hoping the annotation would turn Turing's mystical presentation into something cleaner. It does, to some extent, but still not as good as more modern textbooks do.

With all that said, kudos to Charles Petzold for this wonderful little book!

[Charles · Rating 5 out of 5]

An excellent book on one of the most influential papers by Alan Turing. Petzold does a great job explaining and referencing other works that complement his narrative.

The short bits of history help a lot in understanding the reasoning behind the authors and how they may have reached their conclusions. They also act as short breaks between the explanations.

I think that this is a must-read for any CS undergraduate or graduate student. That said, I strongly believe that anybody that is curious enough, despite his/her background, can find this book interesting and thought-provoking.