FOCS’36 notification
Dear Mr. Turing,
We regret to inform you that your submission
"On Computable Numbers, With an Application to the Entscheidungsproblem"
was not accepted to appear in FOCS 1936. The Program Committee received a record 4 submissions this year, many of them of high quality, and scheduling constraints unfortunately made it impossible to accept all of them.
Below please find some reviews on your submission. The reviews are *not* intended as an explanation for why your paper was rejected. This decision depended on many factors, including discussions at the PC meeting and competition from other papers.
Best wishes,
FOCS 1936 Program Committee
---------------------------------------- review 1 ----------------------------------------
seems like a trivial modification of godel's result from STOC'31
---------------------------------------- review 2 ----------------------------------------
The author shows that Hilbert's Entscheidungsproblem (given a mathematical statement, decide whether it admits a formal proof) is unsolvable by any finite means. While this seems like an important result, I have several concerns/criticisms:
1. The author defines a new "Turing machine" model for the specific purpose of proving his result. This model was not defined in any previous papers; thus, the motivation is unclear.
2. I doubt Hilbert's goal of "automating mathematical thought" was ever really taken seriously by anyone (including Hilbert himself). Given this, the negative result comes as no surprise -- a positive result would have been much more interesting.
3. It's hard to find any technical "meat" in this paper. Once the author sets up the problem, the main result follows immediately by a standard diagonalization argument.
4. The whole philosophical discussion in Section 9, about what it means to compute something, is out of place (even slightly embarrassing) and should be deleted entirely.
Summary: While this paper deserves to be published somewhere -- SODA? ICALP? FSTTCS? -- it certainly isn't FOCS caliber.
---------------------------------------- review 3 ----------------------------------------
merge with alonzo church's submission?
---------------------------------------- review 4 ----------------------------------------
while i agree with the other reviewers' concerns about triviality, i confess to liking this paper anyway. one reason is that, along the way to the main result, the author proves a lemma stating that there exists a "universal machine" (a machine able to simulate any other machine given a suitable choice of input). the claim that this lemma could have "practical" applications is clearly exaggerated -- but even so, it seems like it could be a useful ingredient for other results.
Recommendation: Borderline Accept.
Follow
Comment #1 July 4th, 2007 at 8:49 pm
I found this very hilarious and timely 😉
Comment #2 July 4th, 2007 at 9:07 pm
Dear Colleagues,
I have come to know that recently, Scott Aaronson, the PC Chair of FOCS 1936, disclosed the comments on my 1936 submission to the public. This is extremely annoying. As a PC chair of FOCS 1936, he was supposed to maintain the confidentiality by not disclosing comments on my paper to others.
Disclosing these comments to the public reveals to them that my paper was rejected and this fact embarrasses me!This is a heinous act and I appeal to the community that Scott be hanged for this shameful act.
Yours sincerely,
Alan Turing
Comment #3 July 4th, 2007 at 9:16 pm
Alan: I didn’t know you read my blog! Stay away from them apples.
Comment #4 July 4th, 2007 at 10:42 pm
Scott: They recently provided high speed internet connection in Hell. So all of us are now able to follow your blog on a regular basis!
Comment #5 July 4th, 2007 at 10:48 pm
Kurt: Cool! Does heaven have high-speed as well? And if it doesn’t, then aren’t the two misnamed?
Comment #6 July 4th, 2007 at 11:04 pm
Heaven had internet for generations. Its only now, after constant appealing by all members of Hell (largely complexity theorists) that we also got it in Hell.
Best,
Kurt.
Comment #7 July 4th, 2007 at 11:09 pm
Do complexity theorists go to the first circle of hell or the eighth?
Comment #8 July 4th, 2007 at 11:10 pm
Kurt: Sounds like I’ll have plenty of colleagues to talk to! I’m looking forward to it.
Comment #9 July 4th, 2007 at 11:18 pm
Scott: You’ll have all of’em! there are no exceptions.
djm: isn’t that an obvios question?
Comment #10 July 5th, 2007 at 12:16 am
djm: The more boring complexity theorists go to the first circle. Those who openly use oracles go to the seventh circle with the usurers and others who commit violence against nature, while those who claim that quantum computers can solve NP-complete problems in polynomial time go to the eighth circle (fraud). There are some reports of those who claim to believe NP=P being sent by Minos to the sixth circle with the rest of the heretics.
Comment #11 July 5th, 2007 at 1:34 am
I think there are two gaps in the original “FOCS’36 notification”.
First, Turing would never name the machine he devised after his name; in fact, he named it “automatic machine” in the paper.
Second, according to the Hilbert’s original lecture:
“…
10. Determination of the solvability of a diophantine equation
Given a diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: to devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers.
…”
it seems that he expected there was a postive result.
So Turing’s result indeed came as a surprise.
Comment #12 July 5th, 2007 at 1:49 am
jy: Yeah, I agree that reviewer #2 took liberties with both history and terminology — but do you realize how hard it is to round up half-decent reviewers?
Comment #13 July 5th, 2007 at 1:50 am
Hey, you were religious Kurt, why did you get sent to Hell?
Comment #14 July 5th, 2007 at 3:10 am
that is funny: i had a similar problem with my FOCS’300BC submission “Euclid’s algorithm”.
Comment #15 July 5th, 2007 at 3:15 am
You really hit the nail on the head this time Scott. Good post!
Comment #16 July 5th, 2007 at 4:59 am
They accepted only 4 submissions in a conference/meeting? These 4 submissions must be seminal!
Comment #17 July 5th, 2007 at 5:48 am
Wait a second, mister “Euclid”! How can you possibly have wrote an algorithm in 300 BC? The concpet of algorithm and the very name were created centuries after that, in the Dark Ages by Al Gore!
You’re such a fraud… You must be one of that crackpots that wander around claiming that created his own geometry!
Comment #18 July 5th, 2007 at 5:52 am
Not even right: No, we received 4 submissions. We accepted only one of them, namely “A 7/6+ε Integrality Gap for Optimal Distribution of Gutta-Percha to the Colonies.” This paper was indeed seminal: breaking the 6/5+ε barrier had been an open problem since STOC’29.
Comment #19 July 5th, 2007 at 5:57 am
So Scott, did you submit a paper to FOCS and had it rejected, by chance?
Comment #20 July 5th, 2007 at 6:23 am
This paper was indeed seminal: breaking the 6/5+ε barrier had been an open problem since STOC’29.
It sounds interesting. Have to take a glance at it.
Comment #21 July 5th, 2007 at 6:24 am
Sour Grape: Sure — in fact I’ve had five STOC/FOCS rejections and the same number of acceptances. There are not many things in life about which I can claim to have achieved Zen-like equanimity, but this is one.
Comment #22 July 5th, 2007 at 6:52 am
Very funny.
I recently came up with a mantra I’ll be repeating to myself whenever I get painfully annoying or downright ignorant reviews (which, is far too often…): there’s no such thing as a bad review, just bad reviewers.
Comment #23 July 5th, 2007 at 7:54 am
A variation on conferences:
* rather than accept/reject, have the program committee rank reasonable papers (e.g., those with no known technical flaws and that would be interesting to a significant subset of people attending the conference)
* all papers that receive such a rank are part of the program
* if your rank is poor, you might decide to withdraw the paper to avoid embarrassment (ranks are made public for papers that are not withdrawn)
* although the conference itself would no longer be all that competitive, your goal would now be to rank as highly as possible (and you would include the rank in your CV)
* have people who register for the conference vote on which papers in the program they would like to see presented
Comment #24 July 5th, 2007 at 11:07 am
5 to 5? But the odds of acceptance for a random submission are normally about 33% or less: you need to lower your quality threshold for submission, if you want to reach the standards of your field!
Comment #25 July 5th, 2007 at 11:10 am
3. It’s hard to find any technical “meat” in this paper. Once the author sets up the problem, the main result follows immediately by a standard diagonalization argument.
A recently solution to an open problem got similar comments. The proof uses a recent breakthrough and as such is rather straightforward: describe the technique, prove that it applies, work out the details, and voila open problem is solved. The comment from one referee was right along the lines above: “negative: technically the proofs are not complicated”.
According to this reviewer our paper would have been better had we found a more complicated way of solving this important question.
Comment #26 July 5th, 2007 at 11:17 am
Actually the problem jy has Hilbert talking about in his qoute wasn’t shown to be unsolvable by Turing but by Matiyasevich in the seventies.
Further nitpicking, Gödel can hardly be called a complexity theorist. If you computer scientists want to lay claim to him you should at least call him a computability theorist.
Comment #27 July 5th, 2007 at 11:22 am
The saddest thing Scott is that review 2 in your list is practically verbatim from a review I got for my FOCS reject this year. Sigh!
Comment #28 July 5th, 2007 at 12:11 pm
Given this, the negative result comes as no surprise
We all have seen a comment like this at one time or another. In fact some of us might even have written a comment like this. Yet, when you think about it, if the result isn’t a surprise it means is a widely held conjecture. Proving a conjecture, even if widely believed to be true is still an important result. See for example the proof of Poincare’s conjecture by Perelman. By now everyone knows it was true, it was “just” the proof that was missing.
Comment #29 July 5th, 2007 at 1:57 pm
Review 3 seems highly plausible, except that it would have been Post’s paper, not Church’s. (Post also defined the TM in precisely the same journal issue as Turing’s paper.)
Comment #30 July 5th, 2007 at 3:45 pm
Off topic, but if your new role as a respectable faculty member still allows you time for debunking bad science, you might enjoy looking at this. Sounds like this company might be using the same play book as D-Wave.
Comment #31 July 5th, 2007 at 5:08 pm
Kurt: As much as I’d love to spend my time arguing with perpetual-motion fanatics, I think I’ll leave this one to the physicists…
Comment #32 July 5th, 2007 at 8:13 pm
Kurt: Before you trash talk dwave again you might want to speak with someone whos actually seen the place and what there doing… ever seen 15 dilution fridges in one room each doing a differenrt state of the art qc expt every month anywhere else? didn’t think so.
Comment #33 July 6th, 2007 at 3:58 am
Darryl: Surely everyone else uses more than one room
Comment #34 July 6th, 2007 at 4:26 am
This made my day.
Comment #35 July 6th, 2007 at 9:27 am
Along the same lines as your blog entry:
http://www.computer.org/portal/site/computer/menuitem.eb7d70008ce52e4b0ef1bd108bcd45f3/index.jsp?&pName=computer_level1&path=computer/homepage/1205&file=profession.xml&xsl=article.xsl&;jsessionid=GT62zQvz4zNjBdqYyrTGsNVZppnqvQncVmhLBg8Xv4kj0Byv81KB!-135557833
Comment #36 July 6th, 2007 at 9:28 am
Oops I am sorry for the ugly looking link.
Comment #37 July 6th, 2007 at 3:09 pm
“that is funny: i had a similar problem with my FOCS’300BC
submission “Euclid’s algorithm”.”
That’s remarkable! Well, not the fact that Euclid had his algorithm rejected, but the fact that the participants had enough presence of mind to call the conference “FOCS ‘300BC”!!
Comment #38 July 6th, 2007 at 3:48 pm
“Talent hits a target no one else can hit. Genius hits a target no one else can see. ” — Arthur Schopenhauer
Comment #39 July 6th, 2007 at 3:57 pm
Death to communism!
Comment #40 July 6th, 2007 at 4:47 pm
Hey John, any clues to solving the P=NP problem?
Comment #41 July 6th, 2007 at 5:48 pm
You mean the P≠NP problem?
Comment #42 July 6th, 2007 at 6:29 pm
Scott: I think I should have raised it more properly.
John: Any clues to proving or disproving P=NP?
I am not sure if John is able to give us any clues on that as he should be living in a dimension different from ours.
Comment #43 July 6th, 2007 at 7:31 pm
Scott: I like simple but elegent work at least as much as technically difficult ones, and more frequently the former have a big impact in a long run. I believe that I’m not the only one thinking this way.
FOCS/STOC papers could be important especially when one is looking for jobs. But since you just passed that stage, I hope this FOCS rejection, a highly probabilistic decision, don’t affect your own style of research in the least. It’ll be very disappointing if you start to aim at the number of FOCS/STOC papers instead of really good research (whatever that exactly means in your mind).
Comment #44 July 7th, 2007 at 9:18 am
Re: #29
“Post’s paper, not Church’s. (Post also defined the TM in precisely the same journal issue as Turing’s paper.)”
I am NOT that Post. I keep telling you that. So stop sending me those unpaid bills.
I have, in fact, seen a friend’s QM paper rejected, with 1 referee saying that the results were obviously impossible, 1 referee saying that the results were obviously true but well-known, 1 referee saying that the results were theoretical and an experiment should be done (said experiment was proposed in the paper).
My fiend formally appealed. They got 3 more mutually contradictory reviews. So the editor rejected the paper, on the grounds that referees could not reach a consensus.
My friend then applied for a grant to do the experiment. The grant was denied.
1 referee saying that such an experiment was obviously impossible, 1 referee saying that such an experiment was obviously easy but well-known, 1 referee saying that the such an experiment was useless on theoretical grounds.
Consider the list of distinguished scientists never winning a Nobel Prize. Or the distinguished literary authors never winning a Nobel Prize. I point out that Sir Arthur C. Clarke (Peace Prize A-list candidate) and Bob Dylan are long overdue.
“I’ll let you be in my dream, if I can be in yours.”
-Bob Dylan
Obviously a recursive issue here.
Comment #45 July 7th, 2007 at 10:32 am
Very funny … And you probably won’t see this, which is okay really… (blame John at Thoughts in a Haystack) you’re tagged!.
Comment #46 July 8th, 2007 at 8:20 am
Given your God posts on this blog, I was wondering what you think of this?
http://mindrosity.blogspot.com/2007/07/justintv-vs-god_07.html
Comment #47 July 8th, 2007 at 10:28 am
Re: #46
The text of that blog citation is:
” Justin.tv vs God
Does lifecasting compete with religion as a way to keep you well-behaved? Does it also encourage people you meet to treat you better than they normally would?”
“Religious people are careful about their actions because they believe that God is always watching them.”
“With lifecasting, you are being watched all the time also. In essence, the viewers play the role of God.”
I’d point out that, at least here in the USA, many children for many generations survived a beta-test:
Fred Coots was a prolific songwriter. In the course of his long career he wrote over 700 songs, including the classic Christmas carol “Santa Claus is Coming to Town”, a collaboration with lyricist Haven Gillespie, written in 1934 (there was a second colloboration with Gillespie in 1938, “You Go To My Head”).
You better watch out, you better not cry.
Better not pout, I’m telling you why:
Santa Claus is coming to town!
He’s making a list, and checking it twice;
He’s gonna find out who’s naughty and nice.
Santa Claus is coming to town!
He knows when you are sleeping,
He knows when you’re awake,
He knows if you’ve been bad or good,
So be good for goodness sake!
Oh! You better watch out, you better not cry.
Better not pout, I’m telling you why:
Santa Claus is coming to town!
Now, in terms of Complexity Theory, “He’s making a list, and checking it twice” does not sound like an optimum algorithm UNLESS it is a nondeterministic algorithm, and “checking it twice” is fine-tuning an overall parameter.
Why does Santa Claus use a list rather than some other data structure, as, for instance, what’s under the Christmas Tree is more like a Heap?
The other connection between Santa Claus and Computer Science sprang from the fertile imaginations of Matt Groening (developer) & David X. Cohen (developer), David X. Cohen (writer) and Jeff Westbrook (staff writer).
“Futurama” Xmas Story (1999)
Santa Claus Robot: Fry and Leela, you’ve both been very naughty! I checked my list!
Fry: Well, check it twice!
Santa Claus Robot: I perform over fifty mega-checks per second!
As a comment on IMDB puts it: “Xmas Story” is arguably the greatest episode of “Futurama” ever made. John Goodman guests as a robotic Santa Claus who, according to the Professor, “invariably judges everyone to be naughty” (except, apparently, Dr. Zoidberg). When Fry angers Leela and goes out to buy her the perfect present, both their lives wind up in danger when Santa Claus comes to town. Every year, this episode must be watched, and it will be loved by numerous people because it is hilarious, well-written, and carries more of a message than any other episode in the whole series. In addition, all the actors are at their best, especially John DiMaggio as Bender, John Goodman as Santa, and Conan O’Brien as his own disembodied head (“Oh! Looks like somebody forgot to feed Max!”
I also cite the great Harlan Ellison story “Nackles”, a sort of Inverse-Santa Claus analysis, but CBS nixed the Christmas story featuring Ed Asner playing a racist Santa Claus.
Harlan quit his staff writing job at the New Twilight Zone in protest because the network would not air that episode. The network considered that his idea of Santa Claus being black was too controversial for tv.
For detailes, see Slippage Harlan Ellison (Mark V. Ziesing 0-929480-75-9, Apr ’97 [Jun ’97], $75.00, 361pp, hc, cover by Jill Bauman); Collection of 25 items, most stories, all previously uncollected. One story is by Donald E. Westlake, accompanied by an essay and teleplay by Ellison. This is a slipcased, limited edition with a signed and numbered plate pasted in; four items are available only in this edition.
# 207 • The Deadly “Nackles” Affair • ar Twilight Zone Feb ’87
# 219 • Nackles [as by Curt Clark] • Donald E. Westlake • ss F&SF Jan ’64
# 227 • Nackles • pl Twilight Zone Feb ’87
Also, Harlan’s “Santa Claus vs. S.P.I.D.E.R.” — “It was half September when the red phone rang … When Kris emerged from the dropshaft, Miss Seven-Seventeen’s eyes grew round. He came toward her, with the easy, muscled stride that set him so far apart from the rest of the agents. (Most of them were little more than pudgy file-clerks; where had she ever gotten the idea that espionage was a line of work best suited to Adonises?…”
Comment #48 July 9th, 2007 at 1:12 pm
#47, my blog post is semi-serious, a bit of a look at a future with declining religious belief and some thought about what might replace it (or perhaps what might complement weak religious belief).
Also see this discussion:
http://preview.tinyurl.com/34kb6e
As for relevance to Computational Complexity, I’m sure interesting algorithmic problems will come up in automatically identifying bad behavior in lifecasts so that everyone will know about it.
Comment #49 July 9th, 2007 at 3:21 pm
Anon 43: “FOCS/STOC papers could be important especially when one is looking for jobs. But since you just passed that stage, …”
All the others burn in hell.
Goedel, Turing, von Neumann included. Unfortunately Euclid could not join the company, since he is in Olympus. Not to mention that he is still looking for a permanent position and he is still waiting for his first FOCS/STOCS accepted paper.
PS1. Yes, Euclid is still submitting papers! If this is the question 🙂
PS2. Excellent post Scott. You made your point as clear as possible.