9 ms·

Turing

49 points by draegtun 14y ago

michael_dorfman 14y ago
But his paper “On Computable Numbers, with an Application to the Entscheidungsproblem” (the one that gave the world the Turing Machine) has a bug in it. In fact, it has two. The first is obvious enough that I spotted it when i read the paper for the first time. The second bug is rather more subtle (but still fixable. It’s okay, the field of computing is not build on sand). I'd love to see the identification of these-- it seems quite perverse to mention them in a blog posting without at least a footnote giving the details.
- praptak 14y ago
  There was not enough space on the margin of Turing's paper to describe the bug.
- evolve2k 14y ago
  Anyone have link to the paper?
  - bru 14y ago
    There you go: www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
    - ColinWright 14y ago
      Clickable: http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
- pdcawley 14y ago
  Where's the fun in that? The first bug is pretty blatant and will leap out at you if you're reading the paper closely (it's of the order of a syntax error). Describing the second would have taken too much space, diverted from the thrust of the post and, most pertinently, required digging a book out of one of far too many identical, poorly labelled, cardboard boxes.
zitterbewegung 14y ago
Well, yes papers do have bugs in them but it takes much more time for people to figure it out. Thats really missing the point of the paper. There are bugs you can recover from (typos) and there are bugs that you can't. If you have too many bugs though then academics will be more and more suspicious. The main reason these can remain out in the wild is that there are much fewer eyeballs that look through papers. There are even subtle bugs that pass peer review. Other people have corrected the bugs. Whats even more interesting is that other people were approaching the same problem around the same time * Church with the lambda calculus (with Turing he developed the Church-Turing thesis. * Emil Post with his Post-Turing (note that he had horrible publishing luck, if his luck was better then we would be celebrating 116 years of Post ). Also, post seemed to have died of a heart attack for a electroshock treatment for depression so it seems that he also has an unfortunate demise. At least Alonzo Church died of old age.
- swombat 14y ago
  Seems like you completely missed the point of the article, which was not to claim that papers should be bug-free, but to celebrate Turing and also point out that even the most intolerant "just write it bug-free the first time" genius could let slip some bugs in a seminal paper (whether they're trivial or not is irrelevant).
schrototo 14y ago
As far as I remember, Turing's original paper had a couple of errors, which is why he published a correction very soon afterwards.
tzs 14y ago
For those interested in reading “On Computable Numbers, with an Application to the Entscheidungsproblem”, I recommend doing so via Charles Petzold's "The Annotated Turing". Petzold's book presents the paper, with annotations, historical context, and biographical information. The actual text of the paper is set off with a different background so there is never any confusion as to whether you are reading Turing's words or Petzold's annotations, and so you can easily switch between reading the paper in all its glory, or falling back on the annotations.
- brown9-2 14y ago
  Thanks for the recommendation, this sounds fascinating. By any chance have you also read "Godel's Proof" by Ernest Nagel and James Newman? http://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814758371/ref=lh_ni_t http://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814... It sounds very similar in scope.
- pdcawley 14y ago
  I read it in Copeland's "The Essential Turing", which I recommend highly.
chj 14y ago
In turing's time, I believe that is economically correct not to waste computer time in assembler. You can hire two persons to assemble the program and compare the output. The computer should be doing the number crunching which is really the hard part for human. I am afraid the author failed to appreciate Turing's insight at the dawn of computing.
- deleted 14y ago
  [deleted]
simonbrown 14y ago
Also, it seems strange given that he once said: Instruction tables will have to be made up by mathematicians with computing experience and perhaps a certain puzzle-solving ability. There need be no real danger of it ever becoming a drudge, for any processes that are quite mechanical may be turned over to the machine itself. from https://en.wikiquote.org/wiki/Alan_Turing https://en.wikiquote.org/wiki/Alan_Turing
lcargill99 14y ago
I heard the explosion for writing an assembler attributed to Von Neumann, not Turing.
- pdcawley 14y ago
  Yup. My bad. Hashing collision in my brain.
gms7777 14y ago
From a comment on the page, if anyone missed it: "This story is true, and the conclusion too, except that it was Von Neumann, not Turing, deriding such a tool as a waste of computer time for clerical work. Turing, in stark contrast to Von Neumann[1], understood very well the benefits of using the computer to work at higher level abstractions. In his lecture to the London Mathematical Society about his Automatic Computing Engine[2], Turing sketches out computers not just assembling programs themselves but actually deriving the programs themselves. Your disagreement here is with Von Neumann, not Turing. Turing would have been on your side." [1] https://www.google.com/search?q=von+neumann+clerical+work https://www.google.com/search?q=von+neumann+clerical+work [2] www.vordenker.de/downloads/turing-vorlesung.pdf
- pdcawley 14y ago
  A very useful comment, that. I've added an update to the bottom of the post. I'd always found the assembler story surprising give Turing's history of mechanising drudge work (the bombes, for instance) and now I know why.

49 points by draegtun 14y ago

But his paper “On Computable Numbers, with an Application to the Entscheidungsproblem” (the one that gave the world the Turing Machine) has a bug in it. In fact, it has two. The first is obvious enough that I spotted it when i read the paper for the first time. The second bug is rather more subtle (but still fixable. It’s okay, the field of computing is not build on sand). I'd love to see the identification of these-- it seems quite perverse to mention them in a blog posting without at least a footnote giving the details.

praptak 14y ago
There was not enough space on the margin of Turing's paper to describe the bug.
evolve2k 14y ago
Anyone have link to the paper?
- bru 14y ago
  There you go: www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
  - ColinWright 14y ago
    Clickable: http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
pdcawley 14y ago
Where's the fun in that? The first bug is pretty blatant and will leap out at you if you're reading the paper closely (it's of the order of a syntax error). Describing the second would have taken too much space, diverted from the thrust of the post and, most pertinently, required digging a book out of one of far too many identical, poorly labelled, cardboard boxes.

zitterbewegung 14y ago

Well, yes papers do have bugs in them but it takes much more time for people to figure it out. Thats really missing the point of the paper. There are bugs you can recover from (typos) and there are bugs that you can't. If you have too many bugs though then academics will be more and more suspicious. The main reason these can remain out in the wild is that there are much fewer eyeballs that look through papers. There are even subtle bugs that pass peer review. Other people have corrected the bugs. Whats even more interesting is that other people were approaching the same problem around the same time * Church with the lambda calculus (with Turing he developed the Church-Turing thesis. * Emil Post with his Post-Turing (note that he had horrible publishing luck, if his luck was better then we would be celebrating 116 years of Post ). Also, post seemed to have died of a heart attack for a electroshock treatment for depression so it seems that he also has an unfortunate demise. At least Alonzo Church died of old age.

swombat 14y ago
Seems like you completely missed the point of the article, which was not to claim that papers should be bug-free, but to celebrate Turing and also point out that even the most intolerant "just write it bug-free the first time" genius could let slip some bugs in a seminal paper (whether they're trivial or not is irrelevant).

schrototo 14y ago

As far as I remember, Turing's original paper had a couple of errors, which is why he published a correction very soon afterwards.

tzs 14y ago

For those interested in reading “On Computable Numbers, with an Application to the Entscheidungsproblem”, I recommend doing so via Charles Petzold's "The Annotated Turing". Petzold's book presents the paper, with annotations, historical context, and biographical information. The actual text of the paper is set off with a different background so there is never any confusion as to whether you are reading Turing's words or Petzold's annotations, and so you can easily switch between reading the paper in all its glory, or falling back on the annotations.

brown9-2 14y ago
Thanks for the recommendation, this sounds fascinating. By any chance have you also read "Godel's Proof" by Ernest Nagel and James Newman? http://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814758371/ref=lh_ni_t http://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814... It sounds very similar in scope.
pdcawley 14y ago
I read it in Copeland's "The Essential Turing", which I recommend highly.

chj 14y ago

In turing's time, I believe that is economically correct not to waste computer time in assembler. You can hire two persons to assemble the program and compare the output. The computer should be doing the number crunching which is really the hard part for human. I am afraid the author failed to appreciate Turing's insight at the dawn of computing.

deleted 14y ago
[deleted]

simonbrown 14y ago

Also, it seems strange given that he once said: Instruction tables will have to be made up by mathematicians with computing experience and perhaps a certain puzzle-solving ability. There need be no real danger of it ever becoming a drudge, for any processes that are quite mechanical may be turned over to the machine itself. from https://en.wikiquote.org/wiki/Alan_Turing https://en.wikiquote.org/wiki/Alan_Turing

lcargill99 14y ago

I heard the explosion for writing an assembler attributed to Von Neumann, not Turing.

pdcawley 14y ago
Yup. My bad. Hashing collision in my brain.

gms7777 14y ago

From a comment on the page, if anyone missed it: "This story is true, and the conclusion too, except that it was Von Neumann, not Turing, deriding such a tool as a waste of computer time for clerical work. Turing, in stark contrast to Von Neumann[1], understood very well the benefits of using the computer to work at higher level abstractions. In his lecture to the London Mathematical Society about his Automatic Computing Engine[2], Turing sketches out computers not just assembling programs themselves but actually deriving the programs themselves. Your disagreement here is with Von Neumann, not Turing. Turing would have been on your side." [1] https://www.google.com/search?q=von+neumann+clerical+work https://www.google.com/search?q=von+neumann+clerical+work [2] www.vordenker.de/downloads/turing-vorlesung.pdf

pdcawley 14y ago
A very useful comment, that. I've added an update to the bottom of the post. I'd always found the assembler story surprising give Turing's history of mechanising drudge work (the bombes, for instance) and now I know why.