Blog » Turing's Euclidean Stroke of Genius
Posted on 1235926235|%A: %d %B, %Y|agohover
Everybody knows Alan Turing was the father of the computer. What is less appreciated is that Turing stands right next to Euclid in the pantheon of creative geniuses. What is almost never mentioned is why Turing deserves so lofty a ranking.
I'm an autodidact, so I don't know how the computer science curriculum is usually organized, but I would guess that students learn about Turing machines relatively early in their education, once they have mastered a few programming languages. I've been through a half dozen or so texts on theoretical computer science that cover this ground. They all have one thing in common: they utterly ignore Turing's fundamental insight!
Such texts teach the machine; one learns that a Turing machine involves a "tape" that slides about, with a read/write head, etc. So the student memorizes, works exercises, and comes away with a nice, formal notion of computation in terms of an abstract machine. That's the way I learned it, any way, and it seems to be the way most textbooks teach it.
Now that's a fine thing, and it explains how computers work, and how some things are "computable" and some not, and so forth. It's all very clever, but it's also entirely formal. I didn't come away from it thinking that Turing was anything but a very clever mathematical engineer. In fact the lambda calculus seems much more elegant and simple than all this business of tapes, machine states, and so forth. Turing seemed to me to be a little like Henry Ford or Thomas Edison: an inventor of a useful machine. An ingenious inventor, but still just an inventor. Studying Turing machines never gave me the feeling that I was in the presence of genius; I would have ranked many mathematicians far ahead of Turing.
Then I came across Robert Soare's paper Computability and Recursion and realized that I was getting only half the story. I'm not competent to judge the paper's technical merits, but I can confidently recommend that it should be required reading for anybody studying either Turing machines or the lambda calculus, if only for its excellent account of the history of the concepts of computability and recursion. It's really more an essay in the history of ideas than a technical paper.
The key point Soare makes, although he doesn't express it in quite this way, is this: it's all about intuition, and intuition is all about lived, human experience. The formalism of the machine comes after the leap of imagination that allowed Turing to crystalize intuitions about human experience in formal terms. Soare points out that Godel was unconvinced by Church's recursive model of computation precisely because it was unconnected to intuitions derived from lived experience.
It turns out that the key section of Turing's landmark 1936 paper, On computable numbers, with an application to the entscheidungsproblem, is section 9, wherein he grounds his formalism in an attempt "to show that the 'computable' numbers include all numbers which would naturally be regarded as computable". The next sentence strikes at the heart of the matter: "All arguments which can be given are bound to be, fundamentally, appeals to intuition, and for this reason rather unsatisfactory mathematically." In other words, we have certain real-world experiences calculating numbers, and based on that experience, we have an intuition that some numbers are just "naturally" computable. Now the previous eight sections of his paper described his Turing machine; his observation here amounts to an admission that there is a fundamental rift between our intuitive notion of naturally computable and the numbers computable by his machine formalism. On the one hand, it's not enough to just have a warm fuzzy feeling that the machine can compute everything we think is naturally computable; on the other hand, we can never prove that it can, since intuitions based on experience are not mathematical objects.
Turing's stroke of genius was to do for the experience of calculating what Euclid did for the experience of extensionality in space: he found a way to think about that experience in terms of an ideal, formal imaginative structure whose faithfulness to intuitive experience is indisputable. Euclid came up with notions like a point with no height or width and a line with width but no height; such ideas can never be proven to represent real space, but the intuition that they do is so compelling that it must be accepted. Turing did exactly the same thing for the experience of calculating, literally with pencil and paper.
Most of section 9 of his paper is devoted to describing the work of a human "computer". As Soare points out, in the mid-thirties the term "computer" meant a human engaged in calculation. Turing analyzed the process involved in such calculating. Post-Turing, it's easy to underappreciate what an imaginative leap this was. Calculation by a human, with pencil and paper, is essentially an analog process. If it doesn't look like that to you today, it's only because of the revolution in thought brought about by Turing. (Evidence: Godel couldn't come up with it.) He looked at the process of calculating by writing stuff down on a piece of paper divided into squares "like a child's arithmetic book", and essentially realized that we can model that analog process as a finite discrete process, a sequence of "'simple operations' which are so elementary that it is not easy to imagine them further divided." He furthermore realized that we can model the human computer's "state of mind" in finite, discrete terms. With a few other simple constraints we end up with a formal imaginative model of the work of the human computer that can be directly "mathematicalized"; we can "construct a machine to do the work of this computer", and that machine will correspond naturally, intuitively, and directly to the lived experience of performing a calculation. Turing's machine is to the experience of calculation as Euclid's one dimensional line is to the edge of a straightedge.
The sad thing is that section 9, although it is the heart of Turing's argument, is very simple; but I've yet to come across a text on theoretical computer science that even mentions it. You don't really even need mathematics to understand it, and yet it is the foundation of a massive revolution in human thinking. If a number is computable by a Turing machine, and a Turing machine is a formalization of intuition, then what does "number" mean? For Euclid, number was synonymous with length (which is why the Greeks could not stomach zero as a number); post-Turing, (computable) number is synonymous with the process of computation. For Euclid, numbers say something about extension in space; post-Turing, numbers say something about thinking - Turing's machine models the process of human computation; human computation is a thought process; therefore Turing machine is synonymous with mind. Etc. etc.
In the popular mind this sort of stuff often comes up as the question of whether or not computers can think, which most people probably think of as whether or not computers can simulate human behavior. But the real question is the other way around: is thinking essentially computational? Not so different from asking whether space is essentially geometric.
Like this entry?
on iPhone, iPad, AppleTV, PC. It's free.
Leave a comment
Though it might not be mentioned in standard computer science text books, Daniel Dennett has made essentially this exact point before, though without the connection to Euclid. I believe it's in Darwin's Dangerous Idea.
Dennett did speak to this and to clarify, this (or something very similar) was Turing's Strange Inversion of Reasoning, which was strikingly similar to Darwin's.
It reads: "To be a perfect computing* machine, one does not need to know arithmetic."
Indeed that is the point. And to do geometry, one does not need to be able to draw a straight line.
It's of course not a new insight; it's right there in black and white in Turing's original paper. But it is vastly underappreciated (IMHO) and rather more subtle the might first appear. What seems obvious to us now took an extraordinary bit of imagination.
IOW you're saying that Turing formalized and explicated our notion of calculation, as Euclid did to our notions of distance and direction.
I'd be little more precise: he didn't formalize our ideas of calculation, but our intuitions based our our experience of calculation. It's a subtle but crucial distinction.
the turing machine is more like one of einstein's thought problems. the bit of idealization really comes in where the tape is described as infinite — a physical impossibility, but useful for conceptualizing something like infinity where the possible outcomes of sets of simple programs are discussed in absolute terms (absolute space was newton's schtick; if one is to dispense with infinity in favor of some practical electronic arrangement more like swapping processed values back and forth between two memory registers, what becomes important is that information in a turing machine is really propagating through a 1-dimensional medium — another idealization with no direct physical corollary. einstein's theory is really a theory of geometry and to describe time as a fourth dimension with some special attribute that differentiates it from the spatial dimensions is not precisely what einstein said about time). there are some fun geometries where there are no such things as parallel lines.
But Turing's machine did not involve an infinite tape, and he only made it one-dimensional because two dimensions are not essential to calculating. He could have made it a notebook with one symbol per page, but he made it a tape because that makes it easier for a human to refer back to previous results, within finite limits. He was careful to imagine the computing process in finite terms. The difference with Einstein's thought experiments is that no human could possibly live the experiences Einstein imagined, whereas Turing modeled ordinary experience. Same thing goes for non-Euclidean geometries: they're mathematical intuitions, not experiential intuitions.
in the abstract the halting problem requires — in principle — the possible availability of an infinite memory store for the machine to be complete.
Does nobody remember him?
Sure, I remember him. He had a chain of software stores in the 90s. :-) Soare mentions Babbage (p. 288); apparently his machine encodes Turing computable functions. But he didn't (so far as I know) develop a theory of computation.
It's clear you're not a mathematician; I think you've stumbled upon the concept of 'axiom'.
As for 'intuition', it's not metaphysical. Humans are machines grounded in the axioms that define this universe.
It's clear you've not studied philosophy. Metaphysical = without form or physical substance. Nothing more. Intuition is such. Axioms are as well, in so far as by definition they are not susceptible to proof or disproof. In contrast to such is logical empiricism, which calls upon a rational, provable world. Thus, axioms, being not this, are abstracted beyond the physical world = metaphysical. The author's discussion remains valid.
"Humans are machines grounded in the axioms that define this universe."
…but Godel proved that systems complex enough to be self-referential (i.e. to reason about their axiomatic structure) have an infinite number of axioms, and others following him (e.g. Chaitin) have shown that the axioms must be infinite in kind (not just trivial syntactic extensions of previous axioms). Therefore humans (or at least their possible mental states) are infinite, by your own mechanist reasoning. Anything infinite is quite metaphysical, by definition.
It's true that one of his primary concerns in defining his machines was that their operation be simple and intuitive - Church beat Turing to the draw to some extent with the Lambda Calculus, but his professor argued the value of publishing Turing's paper based on his novel approach. But their are lots of interesting implications from Turing's paper.
Especially with his appendix showing the equivalence of his machines with the Lambda Calculus, Turing made it very evident that any system of a certain level of power had the same capabilities in terms of computation - including the human mind. The implication that the human mind can be modeled by a turing machine or any other kind of computer was the fuel that fed the fire of research in theoretical Computer Science for at least the following 3 decades.
Turing's paper is still not an easy read. I recommend Charles Petzold's 'Annotated Turing' (2008), especially for the historical background.
Hi Darryl - I'll definitely hunt down a copy of Petzold's book. The amazing (to me) thing about Turing's paper is that even though much of it is over my head, the key bits about intuition and the imagined human computer are quite accessible. I wouldn't be surprised if section 9 could be used to good effect in a high school class, with a little bit of accompanying explanation.
Thanks,
gregg
This is fascinating and fun to read about. Thanks for posting this.
The problem with the converse of Turing's observation about human computation, that human thought could be nothing but computation, is a frightening prospect. It opens the Pandora's Box of fears that our thoughts could be mechanically rendered, processed, altered or reproduced by a machine, with or without our consent.
Steven Pinker mentioned in one his books an alternative: the hypothesis that the brain is composed of neurological organs: the hypothalumus, the pineal glands, the neocortex, and so on. There's evidence that the brain is composed of many "sub-computers" - like a motherboard that has many more processors than the CPU, what with the PCI bridge, the memory controller, DMA/interrupt controllers, etc. So "computation" (a person doing math on paper) could be the result of one section of the brain at work, but other sections do facial recognition, emotion, association, memory processing, vision, and so on.
At a low level, neurons ARE just computation: axons and dendrites tossing volts across synapses.
If you believe in a soul, there's another possibility. The brain is just an organ of computation, but its results are served/returned to the consciousness (which is not the brain) for consideration. This would be like the Buddhist idea that the reality all around you is just an illusion, like the image on a TV screen inside a submarine control room so the pilot & crew can see what's outside the opaque walls of the sub. The image on the screen is not real, but it's a representation of what the optics are recording and trying to render with high fidelity. There really is a giant squid off the starboard bow, but everyone on board knows that shooting a few rounds with their sidearm into the TV monitor on the bridge won't kill the real squid. So the squid is reality. The TV is the image synthesized by the brain from the grainy data obtained from your eyes. You are the captain, the ghost inside your machine. And the crew of the submarine are the component chunks of your brain, obeying (kinda/sorta) your every whim at your command.
But that's just another hypothesis.
Hi Ian,
It's indeed a rather disturbing if not terrifying prospect that we may turn out to be mere computing devices of some sort. I gather Godel could never quite bring himself to believe it. Personally I suspect there will always be some corner of the mind that resists mechanistic explanation; but that may turn out to be small comfort if science can reduce most of the stuff we think makes us human down to machine dynamics. Well, we'll probably destroy the earth before we get to that point, so maybe it doesn't matter. ;)
Thx,
gregg
Chill out guys. We know nowhere near enough about our brains, our mind and our physical universe to make any assumptions.
As long as we can't (literally) get beyond Kant's theory of perception things can go in any direction, or nowhere in particular. Regardless of his beautiful framework Turing's ideas and indeed our modern computers are subject to the same theory of perception.
Steven
Isn't this what Douglas Adams was trying to tell us? ;)
You may get a lot of people posting here who basically want to say, "I knew that already" or "You're doing it wrong." I just wanted to say thank you for highlighting this. You've encouraged me to read Turing's paper.
Hi Shane - Thanks, I appreciate that.
The other key insight, ignored in this article :
That a turing m/c can manipulate abstract meaningless SYMBOLS instead of numbers.
This was a huge insight, becasue everyone till then thot of computers as 'number' manipulators. 1+2 = 3 type stuff.
This insight allowed Turing to do Crptanalysis. And gave us Sketchpad. And Photoshop. And Winamp. And porn DVDs..
Hi av viva - that's true, but I believe it predates Turing by quite a bit. Plus manipulation of symbols by a Turing machine is numeric (mathematical) computation by definition. I.e. string manipulations are just sequence operations. Or to put it another way, syntactic operations are no less mathematical/computational than semantic operations.
-g
For those who wish to study Turning's paper on their own, I would strongly recommend the book "The Annotated Turing" by Charles Petzold. This book does a great job of explaining the intuition behind this paper.
Post preview:
Close preview