The Annotated Turing

I've been 'reading' The Annotated Turing for coming up on two years now. I place 'reading' in quotes, as my approach is not a continuous effort, but rather, a series of frustrated exercises. I started by reading this book from the library, and extended my checkouts a couple of times before I concluded that I needed my own copy to give it proper attention.

The book, by Charles Petzold, is, as the title suggests, an annotation of sorts, of Alan Turing's 1936 paper, On Computable Numbers, with an Application to the Entscheidungsproblem. The paper is a milestone in computer science, even if it precedes most of computer application. In the paper, Turing lays the groundwork to establish what we now take for granted, that it is impossible to 'decide algorithmically whether statements in arithmetic are true or false, and thus a general solution to the Entscheidungsproblem is impossible.'

Turing does this in his paper by a series of logical steps, first describing a hypothetical machine which can carry out various simple instructions, then gradually extending the power of this machine until it is computationally complete, that is, it is capable of generalized computation (much like a modern computer). He then proceeds to show how there is no"process for determining whether a given [machine] is satisfactory or not." In his paper, this means that we cannot determine if a given machine will perform the job it is supposed to (calculate a real number) or not (is 'circular').

Well, the paper is itself filled with lots of mathematical notation in various scripts (German, Greek, what have you), and additionally is compressed, in the sense that much of the notation and discussion assumes familiarity with the field at the time. Rather than read it alone, I thought it would be more enlightening to read the annotated version. As it turns out, this is at times true, and others, frustratingly false.

I try to read difficult papers on my own, as I don't really have the time to take classes right now. But my experience has been that in any difficult subject, I make much better progress if I have an expert in the domain of whom I can ask questions when I get stuck. Here, I was hoping that Petzold would bridge that gap, if not as an expert, than at least as an accomplished tour guide. The material, especially the mathematical foundation, is difficult enough that any ambiguity derails my thoughts immediately.

So I began reading, and enjoyed his introduction of Diophantine equations, and could even see the point in the context of the book. When he began discussing the cardinality of infinities, and tried to describe Cantor's first proof of the non-enumerability of real numbers, I had my first falling-out with this book. Unlike the diagonalization approach, which is very accessible, the first proof is difficult in the extreme (perhaps subtle is a better word), and I found Petzold's explanation opaque and frustrating. I gave up and put the book on the shelf. To be fair, it took Cantor some twenty years to come up with the clearer diagonalization proof, so the problem just ain't easy.

Eventually, I picked the book up again, and tried to retrace my steps. I reread the chapters leading up to the troublesome proof, and once again crashed on the rocks. It was not until I went surfing on the web and found a post by Dick Lipton (a Professor of Computer Science at Georgia Tech) on his weblog discussing the first proof that I was truly able to grasp the point (and the sublety is such that I can understand the fine distinctions which make this proof convincing only in the space of the day I have read Lipton's presentation -- the following day I am once again asking myself "but how???"). This entry supports my notion that access to an expert is sometimes necessary to make forward progress.

The book is not without it's moments of humor. After an ever-escalating tower of abstract machines, Petzold has shown how it is possible to do (binary) addition and multiplication with a 'Turing' machine, at the simple expense of adding dozens of machine configurations and expanding the 'tape' to arbitrary length. It is beginning to dawn on the reader that the primitive hypothetical machine may be extended to a general purpose computer, albeit so primitive as to comprise a bit of a tar-pit. At this point, Petzold shares the understatement: "Obviously, the Turing Machine is not a programmer-friendly medium."

My next stumbling block has only just arisen. I believe I understand the concept of enumerability fairly well, though I acknowledge that any given enumeration can be quite tricky. Petzold covers how Turing has assigned a number to each of his machines by stringing together all the states (machine configurations) of a given machine, along with detected symbols and transition states, to form an encoding, that when translated to digits, gives a unique, finite integer. This is its description number. Since we can enumerate all integers, and we can reject finite integers which are not valid description numbers (given Turing's encoding rules), we can therefore enumerate all Turing Machines.

But this is where Petzold loses me again. I can't agree with his conclusion. He says that since we can enumerate all Turing machines, and some of those Turing machines produce computable numbers, therefore "computable numbers are enumerable." I'll reproduce his conclusion in a complete quote:

By reducing each machine to a number, Turing has also made it possible, in effect, to generate machines just by enumerating the positive integers. Not every positive integer is a valid Description Number of a Turing Machine, and many valid Description Numbers do not describe circle-free machines, but this enumeration certainly includes all circle-free Turing Machines, each of which corresponds to a computable number. Therefore, computable numbers are enumerable.

So

1. Generate each integer in turn


2. Reject integers which are not valid Description Numbers (those which don't follow the rules to describe the states of a true Turing Machine)


3. Reject machines which are not 'circle-free' (these machines can, for instance, get stuck in loops without generating a true real number)

And voila, we are left with the enumeration of machines which generate computable numbers! The trouble is with step three. The whole point of the paper is to show that "there can be no general process for determining" if a machine is circle-free or not. Given that, the procedure for enumerating Turing Machines does indeed exist, but a procedure for enumerating circle-free Turing Machines, and hence for enumerating countable numbers, seems not to be satisfied by this procedure. Have I misunderstood Petzold? Possibly. But once again, I am frustrated by being unable to ask questions.

I'm not putting the book on the shelf for another year, as for the most part, I've been able to follow the elaborations on the paper. In fact, the detailed dissections of the various example machines from the paper have been quite helpful. But I'm just not happy when I encounter these stumbling blocks.

The Return of Sherlock Holmes

I finished The Memoirs of Sherlock Holmes last night. This was the second story collection Renee was reading from last term for school. She didn't have to read the entire book to satisfy her requirements, but I did.

Unfortunately, it is also the short story collection which ends in The Final Problem, the story where Arthur Conan Doyle tried to kill of Holmes so he could move on to other, 'better' works.

I never set myself the goal of rereading this entire collection, but was enjoying it enough that I would take my iPod to bed and read part of a story to get sleepy. Having finished with the death of Sherlock Holmes, I feel that I want to get past that point, and so, I'm starting up The Return of Sherlock Holmes. I'll at least read the resurrection story, The Empty House.

Silver Blaze

Renee had a project to read a bunch of Sherlock Holmes over the last few weeks. She's almost done, but as she started with The Adventures of Sherlock Holmes, I grabbed it from Project Gutenberg and followed along on my iPod Touch. She then started on The Memoirs of Sherlock Holmes, and I just finished the first story, The Silver Blaze. I don't think that she's going to read the entire collection this time, but I'll probably work through it slowly as it is a pleasant nostalgia trip for me.

Moonraker

I just finished Moonraker tonight. I've been taking it at an easy pace, a chapter a night or less, so about a month has passed since I bought it. I really enjoyed reading a chapter a night before coming to bed. And I will say that following the chronology, it is in fact the best book so far. I'm looking forward to the next one, Diamonds Are Forever.

Moonraker

Moonraker has already piqued my interest. In the first few pages, we get a glimpse of the bureaucratic hierarchy in which James Bond operates. He has an office shared with two other '00's, 008 and 0011, and is the senior '00'. Here are some snippets that give a flavor of his routine between adventures.

He shrugged his shoulders and resolutely opened the top folder [of intelligence reports]...

It was the beginning of a typical routine day for Bond. It was only two or three times a year that an assignment came along requiring his particular abilities. For the rest of the year he had the duties of an easy-going senior civil servant...

He took no holidays, but was generally given a fortnight's leave at the end of each assignment--in addition to any sick-leave that might be necessary... He had a small but comfortable flat off the King's Road, an elderly Scottish housekeeper--a treasure called May--and a 1930 4 1/2-litre Bentley coupe, supercharged .. so that he could do a hundred when he wanted to.

...It was his ambition to have as little as possible in his banking account when he was killed, as, when he was depressed, he knew he would be, before the statutory age of forty-five.

Eight years to go before he was automatically taken off the 00 list and given a staff job at Headquarters. At least eight tough assignments. Probably sixteen. Perhaps twenty-four. Too many.

Those last two segments give us the tidbit that by the time of Moonraker, Bond is around 33 years old, and can look forward to having episodes of torture into his mid-forties.

The chapter closes out with a description of Bond's progress through a pile of memos, ticking them off, initialing them '007' and putting them into the out tray for the next bureaucrat. It really tickles me to see him outside the frame of action. It's like watching Superman relaxing in the Fortress of Solitude with a model kit, or working his taxes on a crummy too-old laptop.

Live and Let Die

I just finished Live and Let Die a few days ago. I've read quite a few Ian Fleming novels over the years, but at least a decade has passed since I last read one, so I've gotten the urge to read them all in chronological order. As already noted, I'd finished Casino Royale and enjoyed it quite a bit. It's been long enough, that with my memory, each book seems quite new.

I found a review on Amazon for Live and Let Die that contained the following snippet:

I would rank "Live and Let Die" in the second-tier of Bond novels, along with "From Russia, With Love" and "Moonraker." It doesn't quite reach the level of such absolute masterpieces as "Doctor No," "On Her Majesty's Secret Service," or "You Only Live Twice," but it's certainly superior to such relatively weak entries as "Goldfinger," "Casino Royale," and the disastrous "The Man with the Golden Gun." All in all, a classic Bond thriller.

I have to agree with A. E. Kaiser that Live and Let Die is a better book than Casino Royale. CR is not a bad book, by any measure I'm willing to apply. It's just that by the second novel, Fleming's already begun to get a much more three-dimensional brush stroke for his character and the world in which he maneuvers.

Seeing as how the next book in the sequence is Moonraker, which A. E. Kaiser puts into the second tier, I'm quite anxious to get started! And given that I can apparently identify the movie version of Doctor No in three notes, I'm not sure I want to wait for that 'absolute masterpiece' to roll around in the chronological sequence. But of the two intervening novels (Diamonds Are Forever and From Russia, With Love), the second is also in the second tier, so I'll struggle to hang on.

Sun in a Bottle

I'm just finishing up Sun in a Bottle by Charles Seife. He covers the pursuit of fusion power from the early awareness of radioactivity, through the construction of fission bombs, onward to fusion research (magnetic confinement, inertial -- laser -- confinement) and fringe science, such as cold fusion, sonoluminescence and electrostatic confinement (fusors).

[Update One: The above paragraph sounds pretty pejorative, and it is. Seife takes pains to describe how easy it is to mistake the signs of fusion, and how easy it is to become emotionally invested in the results of these smaller experiments. But he is pretty clear that the evidence is not there. I'm not going to become a champion for either side. I just read a book, people.]

It's a fascinating book, and coincidentally, I've been sitting on a video that was made a couple of years ago at Google featuring Robert Bussard. The video is called Should Google Go Nuclear? Clean, cheap, nuclear power (no, really). During the talk, Bussard presents his work on electrostatic confinement, and it's a wonderful talk, even if I don't really follow the physics that well. Sadly, Charles Seife mentions this in his book, and puts it in the same category as cold fusion and bubble fusion. I hope he's wrong. Bussard was a fascinating scientist and it would be great if he figured out a path to fusion power before he died.

[Update Two: I'm going to quote the entire paragraph on Bussard, so that M. Simon (another commentor) can judge the tone for himself:

On November 9, 2006, just days before the Olson story broke, the fusion physicist Robert Bussard gave a talk at Google about his research with a modified fusor. He had been working for the navy, but after a number of years he had run out of money for the program. The scientist told his audience that if he could only get his hands on $200 million, he would be able to produce a working power plant within four to five years. Bussard was deceiving himself if mainstream scientific thought is any guide. The equations of plasma physics strongly imply that fusorlike devices are very unlikely to produce more energy than they consume. Nature's inexorable energy-draining powers are too hard to overcome.

Casino Royale

With Quantum of Solace out in the theatre, I had a hankering to revisit the original novel that kicked it all off. Grabbed it a few weeks ago, and I've been reading it evenings before bed since then. Just finished it last night, and it is pretty much as good as I remembered. A bit saccharine in parts, but it's kinda the 'birth' of James Bond. I enjoyed it, and will probably read Live and Let Die before too long.

Oh, and it was amusing to be reminded that Bond's first nemesis organization was SMERSH, a Russian counter-espionage agency which translates to "Death to Spies". And yes, while it had apparently ceased to exist by the era Bond supposedly operated in, it was a real organization.

Day of the Triffids

I finished this yesterday evening before going to bed. If you've seen the film adaptation, or worse, some pastiche emphasizing the ooga-booga creepiness of ambulatory, poisonous carnivorous plants directly or indirectly inspired by 'Triffids', then you might think this a trash novel. In reality, it's a very nice post-apocalyptic novel, with interesting characters and a decent exploration of the consequences of civilization's worldwide collapse.

I especially liked that Wyndham ensured that his protagonist had no omniscient knowledge of the source of the disaster -- almost literally a disaster, by the way. He speculates about it, but no one left alive speaks with certainty of it's source.

Nassim Taleb

We cannot help being fooled by randomness. We're too impressionable. I was in London when the second terrorist attack happened and I automatically behaved like anyone else, ducking for safety. Then I realised that my biggest danger in London came from my jet lag and being used to traffic driving on the other side of the road. We should worry about preventable sources of death. I should worry more about how much sugar I put in my tea than whether I am going to be hit by terrorists. The key is not to try to stop being a fool, but to be aware of when it matters not to be a fool. If you can't do anything about a problem, it's a waste of time analysing it.

Just a quote, to remind me that he has a new book out, The Black Swan: The Impact of the Highly Improbable. I really loved his first book, Fooled by Randomness: The Hidden Role of Chance in Life and in the Markets, so I'm looking forward to this next one.

Camelot 30K

The "30K" in the title of this book stands for "30 degrees Kelvin", pretty cold. Like most books by Robert L. Forward, it is rich in physics puzzles, filled with fascinating xenobiology, and equally weighted with clunker characterization and story. As always, I had to ask myself seriously if I wanted to continue, as it's a battle as to which wins out, the great 'hard' science fiction or the painful fiction.

In the end, I stuck with it, and was rewarded with a wonderfully imagined alien race. Not so much their culture, but their biology and their reproductive cycle. If you like that sort of thing, it might be worth the trouble to read...

Jhereg

Been reading mostly on the Web lately, and lots of technical papers. While I dip into a lot of non-fiction, which you'll occasionally see on the sidebar to this site, I don't usually finish them, as they're generally sorta browsy items. In fact, the last non-fiction item I read cover-to-cover, The Big Con, took me several weeks, even though it was only about 300 pages.

Anyway, I'm now giving in to a spate of fiction reading again. And not just fiction, but fantasy and science fiction. Just finished Jhereg, by Steven Brust. While I've been aware of Brust for years, I've never taken the plunge, being only a lukewarm reader of fantasy. Usually it takes a Roger Zelazny or Gene Wolfe to get me interested. But recently, Cory Doctorow waxed enthusiastic about Dzur, the latest book in Brust's main series, and I decided to take the plunge.

No write-up, follow the link. I'm noting it here so I'll remember which books of his I've read. And yes, it was more than entertaining enough for a light read.

The Big Con

This review is a decent summary of the book I just finished, written by David Maurer in 1940. In The Big Con, what started out as a linguist's attempt to document the argot of a criminal brotherhood became a sociological study and a document of all the popular "big cons". Somewhere out on the Internet I read how this book had served as the inspiration for The Sting, which I'd seen as a kid, and I had to read it.

Nowadays I seldom finish a book, browsing for the highlights instead. But I finished this one. Let that be a testament.

Finance for Non-Financial Managers

The McGraw-Hill 36-Hour Course In Finance for Non-Financial Managers was an interesting book, surprisingly. I have a phobia about financial planning and budgeting, so I'm thankful that my wife is so good at it. But Cooke is an entertaining writer, and in twelve chapters (plus appendices) he introduces many of the concepts of finance, financial reports and budgets. I don't think any of this will stick, but I felt the urge to read it after seeing an article on my company's financial reporting practices (which are mostly well within GAAP boundaries, I'm told).

Search and Return

I tore apart three closets today, working up a dusty sweat. I was looking for a book that the corporate librarian at my workplace said I had checked out. I know I checked it out, say, six years ago! She even offered to renew it for me! Enough time has passed, even, that the book is out of print, superceded by an expanded volume, CJKV Information Processing.

So on the off chance that I'd stored it along with my own Japanese books (kanji dictionaries, course books, manga, etc.) I started tracking down that box. In the end, I found it in the garage, and not in a closet at all. So it goes back on Monday.

On the bright side, I found a box of CDs in one of the closets, including one I'd been looking for for the longest time, Mel & George "Do" World War II. I'm now ripping it into iTunes so's I can listen to it on my iPod tomorrow while tracking insidious bugs...

Stocks and Math

I just finished A Mathematician Plays the Stock Market. John Allen Paulos makes his living popularizing math, but I found this book rather uneven. While I found the middle chapters generally interesting, the beginning was muddled to the point of seeming nonsense at times, and the latter chapters really didn't tell me anything that wasn't already obvious (actually, I knew most of what was in the book, but some chapters were pretty good at illustrating concepts at an intuitive level).

On the whole, I don't think I'll bother with any of his other books.

Jumper

I'd heard Steven Gould's Jumper described as a 'young adult' science fiction novel, and though it's usually spoken of favorably, this categorization had led me to put off reading it. Considering that the central character is a runaway who has been beaten by his alcoholic father, abandoned by his abused mother, nearly raped at a truckstop, and who launches his independence by burgling a bank of nearly a million dollars, I can see why it's such a hit with young adults.

Seriously, this is a classic adolescent power fantasy, viewed through the filter of a rational science fiction writer. Gould tries to imagine what a smart teenager would do with the power of teleportation, short of becoming a megalomaniacal sociopath. Davey Rice of course, coming from a broken home, starts off a little rough, but is genuinely good-hearted, so the story doesn't take too dark a turn. In point of fact, other than the protagonist being a teenage male, I don't think this really is a 'young adult' novel. It's just a decent science fiction novel, and I can imagine myself reading the sequel someday.

Recently Finished Books

Pure Ketchup by Andrew F. Smith. Spurred by the Malcolm Gladwell essay on ketchup, I found this book at the library and gave it a whirl. It's not the sort of book I read in depth, but it was interesting nonetheless. I learned that ketchup was not always confined to tomatoes. There were ketchups for walnuts, mushrooms, fish, pretty much anything you wanted to preserve and use as a sauce. Tomatoes are just the ultimate survivor.

In the trashy science fiction category, I finished Rogue Berserker by Fred Saberhagen a couple weeks ago. This is another in his universe where machines hunt down all life, following their scrambled program from a war millions of years ago. Lightweight as all get out.

Vampire Trailer Trash

I just finished reading Dead Until Dark, the first novel in a series by Charlaine Harris. It's billed as a "Southern Vampire Mystery", but I think Vampire Trailer Trash captures it just fine. It was nice as a change of pace, but I probably won't get around to the second in the series any time soon.

Coalescent

I finished Coalescent by Stephen Baxter, this evening. Unlike the majority of recent 'hard' scifi (or gosh-wow indistinguishable-from-magic-superscience scifi) I have read, this book centers around biology, evolution and sociology for it's scientific underpinnings. While it took me most of the nine week library renewal cycle to finish it, it was nevertheless quite intriguing. By the time I finished it, I had had that sense of wonder reaction that science fiction is sometimes capable of invoking.

I hear there's a sequel. Perhaps I'll look for it sometime.