Sunday, June 6, 2010

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.


  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.

No comments:

Post a Comment