Hi again,
It’s been a little longer than I would like since my last post, but we’ve been taking turns getting sick in my family and it’s slowed me down a bit. Well, this is wishful thinking but maybe it will help build up my immune system for the upcoming outbreak of avian flu.
Since this is Halloween, I thought I’d post about something befitting the occasion, computer science’s own version of the occult. Or, since discussions of the differences between ID and science are quite popular on the blogosphere now, maybe we should refer to this as our own version of intelligent design. But first…
One of my favorite recreational pages on the Web is Gerhard Woeginger’s P vs. NP Page. Not surprisingly, a lot of the entries on this page would appear to be the work of crackpots. However, many others of these were (seemingly) serious attempts at a proof by academics. Perhaps the most illustrious P vs. NP author appearing on this page is Selmer Bringsjord, who is chair of the department of cognitive science at Rensselaer Polytechnic Institute.
I can recall seeing much discussion on Usenet and the blogosphere when his paper An Argument for P=NP, co-authored with Joshua Taylor, first appeared last year. A lot of the commentary was of the sort that the paper obviously was a parody, since it’s inconceivable that Bringsjord would actually believe his own ridiculous line of reasoning. It also spawned some investigations into the premises of Bringsjord’s arguments, the best example of which in contained within this article by Scott Aaronson.
I noticed recently that Bringsjord has updated his paper, to respond to some of the feedback it generated. So if it was intended as a joke, it must be of the “long-running” variety. The thing I find most curious about the whole episode, though, is not within the P=NP paper itself. On Bringsjord’s home page, just below a link to the P=NP paper, is a link to the paper The modal argument for hypercomputing minds. In it, Bringsford argues that, er, well, let me just quote from the abstract:
… we give herein a novel, formal modal argument showing that since it’s mathematically possible that human minds are hypercomputers, such minds are in fact hypercomputers. We take considerable pains to anticipate and rebut objections to this argument.
The thing is, the format of this paper, which takes a questionable premise and then uses formal reasoning via modal logic to reach a “remarkable” conclusion, is very similar to the P=NP paper. The conclusion I am tempted to come to is that Bringsjord, in his P=NP paper, is parodying his own work.
What then, should we make of the hypercomputation paper? This paper is published in no less than Elsevier’s Theoretical Computer Science, Volume 317 (June 2004), pages 167-190. This is part of a special issue devoted to “super-recursive algorithms and hypercomputation”. A glance through the table of contents lists a slew of articles with similar subject matter. Has Theoretical Computer Science gone all soft and fuzzy? Perhaps Chris Leonard, if he reads this, would care to comment.
Many of the authors are members of the Hypercomputation Research Network, which seems to be some sort of cabal of sorcerers community of philosophers intent on plumbing the depths of the mind. Certainly nothing wrong with that; I find the philosophy of mind to be a fascinating subject. But perusing several of the articles linked to on this site, I find the level of reasoning to be painfully similar to what Bringsjord uses in his papers.
So what do you think? Do the hypercomputationalists escape scrutiny because they are philosophers and not scientists, and therefore not held to any the same standards? Or are they theoretical computer science’s equivalent of alchemists?
Nice post, Kurt! As far as hypercomputation is concerned, I believe that all of the thus-far proposed models are not known to be physically implementable. It is possible, though, that some day we might have a reasonable model of computation that is more powerful than Turing machines (although, I don’t know how this will look like).I am not a hypercomputation specialist, so I can’t say any further. But, there is a nice (and trustworthy) survey that summarizes the thus-far proposed models of hypercomputation: http://www.amirrorclear.net/academic/hypercomputation.html
Link | November 2nd, 2005 at 8:52 pm
I was recently compelled to publish a paper of mine in Theoretical Computer Science because it was invited to a special issue of some conference. Shortly afterward, I decided that this was the last paper I would publish with an Elsevier journal (due to their horrific price gouging and non-friendly publication practices).How happy I am to see that my well-intentioned paper will join the work of glorified crackpots. Hurrah TCS; now you can take my copyright, make me look like an idiot, and then charge me exorbitantly for your time.
Link | November 2nd, 2005 at 10:55 pm
Anthony (twidjaja) – Thanks for the link, I’ll take a glance at that paper when I have a chance (but you know, Toby Ord is one of <>them<>
).I have more I’d like to say on the topic, but I need to refine my thoughts a little bit first. I’ll try to post again in the next day or two.In the meantime, did you notice that cryptic post by Eray Ozkural on comp.theory? Some <>spooky synchronicity<> going on there!
Link | November 3rd, 2005 at 12:15 am
Anonymous – Being outside of academia, I don’t have much of a feel for publishing matters. I always had the impression that <>Theoretical Computer Science<> was one of the big guns in the theory world, but certainly it and Elsevier have been getting beaten up in the blogosphere lately.But I wouldn’t feel too bad; I’m sure other journals occasionally publish questionable results, too. For example, I see on Bringsjord’s web page that his new paper <>A New Gödelian Argument for Hypercomputing MindsBased on the Busy Beaver Problem<> is due to be published in <>AppliedMathematics and Computation<>, so … oops, wait, that’s another Elsevier journal. Never mind…
Link | November 3rd, 2005 at 12:34 am
I’m no hypercomputation expert either – but articles which appear in our journals are vetted by the editors and referees and Elsevier has little input on what subject matters the journals cover. We prefer to let the communities they serve decide that.As for this particular paper – it is part of a special issue edited by Mark Burgin and Allen Klinger of UCLA. If you would like to discuss the intricacies of the paper, I would suggest they, or Selmer Bringsjord, are infinitely more equipped to engage in a dialogue than myself.Speaking as a publisher, we do encourage our editors to explore the boundaries of science – after all, how else is progress made? However, if there are serious concerns about certain topics, I’ll be happy to investigate further.In response to ‘anonymous’ complaining about the list price of TCS – please take into account the size of the journal when discussing a price. TCS prints over 12000 pages a year, it is naturally more expensive in absolute terms than a smaller journal. I refer interested parties to the University of Bielefeld’s study on journal prices per page:http://www.mathematik.uni-bielefeld.de/~rehmann/BIB/AMS/Price_per_Page.html(Scroll down, it’s number 178)Also, unfriendly publishing practices? I’ll try to change whatever it is that makes the current process unfriendly. Maybe you’d like to drop me a line and we can work something out?Chris
Link | November 6th, 2005 at 9:31 am
Thanks for taking the time to respond here, Chris. I agree with your comments regarding editorial content – clearly my complaints belong with the editorial board and not with the publisher.I do have one complaint regarding the ScienceDirect pricing, though: I was curious about what criteria Burgin and Klinger used in selecting articles, but their editorial at the front of the issue will cost me $30 to view via ScienceDirect. It seems that the author index and the editorial board sections will also cost me $30 each. While I might be willing to pay that amount for (at least some) articles, I think you ought to make those other types of sections (as well as things like forwards or prefaces) freely available.My situation may be somewhat atypical. I don’t have access to a research library, or to an institutional account for on-line resources like ScienceDirect. I can in theory get journal articles from my local library via inter-library loan, but the process can take up to a month, which obviously slows the pace of learning.
Link | November 6th, 2005 at 9:09 pm
Hi Kurt,I agree that the pricing of individual SD articles is somewhat erratic. Actually there is a single price for all articles, despite their size or content – which is clearly flawed for certain items (editorials, board listings etc..)I think you will see a change to this soon, but in the meantime I will be happy to send you a copy of the special issue in question for your personal use.Regards,Chris
Link | November 7th, 2005 at 8:31 am