Spooky science

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?

Religious wars and LaTeX tools

On his blog, Lance Fortnow recently mentioned that for several years he has been happily using Windows instead of Unix. This provoked a lot of fervent comments, some of which are pretty funny.

I try not to take sides in OS debates. I use a Windows PC at home because my wife and I occasionally need to take work home from the office, and that's what is used there. In my youth, I used to enjoy tinkering more with the hardware and software, and for a while I was using a dual-boot Windows and Linux setup. But nowadays I find the whole issue distracting. Computers have become a commodity in the economic sense, but not in a functional sense. When I use my computer, I want to be able to use it as a tool to do my work and not have to give a second thought about what OS I'm using, and how it needs to be tweaked to work properly with my applications, what security patches I need to apply, etc. Application software should be platform independent (to the extent possible), and data should be stored using open standard file formats. We have a long way to go to reach this point.

I really feel let down by Larry Ellison and Scott McNealy. It's been about 10 years since Java and the Internet Appliance were promoted as the solution to this problem, and I'm still waiting. They promised way too much, way too soon, and I think it really soured everyone on the whole idea. But now that broadband internet access is finally becoming widespread, maybe we'll see another attempt at popularizing this concept.

The one thing about the Java phenomenon that has kind of surprised me is that it was seen as primarily a boon for software developers and not hardware developers. I think this should be just the reverse: the JVM totally opens the door for hardware innovation. PCs get a little faster each year, but it's been a long time since we've seen anything truly new in PC hardware. Nor should we expect anything new. PC designers need to accomodate Windows' requirements, and that limits what the engineers can do. But once a critical mass of Java applications exists, the sky is the limit as far hardware is concerned. A JVM will need to be written for each new hardware platform, but this should not be too hard. All the applications, as well as the UI layers of the OS which are themselves written in Java, will immediately transfer to the new hardware. The performance improvements made possible by radically new hardware designs will easily outstrip any inefficiencies introduced by the VM layer. This has yet to happen on the desktop, but I think it is happening to some extent at the small end of the spectrum, in cellphones.

But I digress... Of the comments to Lance's post, of particular interest to me were several that described tools for using LaTeX on Windows. It was reassuring to see WinEdt described as being a nicer editor for handling LaTeX than the Unix-based Emacs (although this is probably not a majority opinion), since this is what I'm going to be using. WinEdt acts as a front-end to the MikTeX software package which does the actual typesetting.

WinEdt is a text-based editor; a couple of WYSIWYG editors were also mentioned in the comments. Scientific Workplace is a commercial package which, due to its high cost, is not an option for me. LyX is an open-source document processor which seems very interesting. Lyx was developed for Unix, but there is a Windows port available. I'm going to stick with WinEdt for now, mainly to force myself to learn LaTeX code, but perhaps in the future I'll take another look at using LyX.

While I'm on the subject of LaTeX, let me mention the books I plan on using to learn this. Learning LaTeX by David F. Griffiths and Desmond J. Highman, and First Steps in LaTeX by George Grätzer, are both tiny texts which promise to get me up and running quickly. I'll let you know how it goes.

My next post will be on graphics tools to provide diagrams for my LaTeX documents. In the meantime, if you have a favorite LaTeX program or book, please let me know!

Scott Aaronson joins the ranks

I usually avoid short posts like this, but here's a bit of news via Michael Nielsen that I thought warranted an immediate mention: Scott Aaronson has started his own blog, Shtetl-Optimized.

And since I had to look it up myself, here is what a shtetl is.