Bertrand Russell once said that a special section of Hell is reserved for those who claim to have refuted Hume on induction. No doubt the same is true for those who think they can evade Gödel's Theorem. I don't believe in Hell, but nonethless I was a bit worried when, over lunch, I came up with what seemed, at first, to be a way of using statistical learning theory to wriggle out of all the usual uncomputability results. (I blame the kimchi.) I wrote it out for a particular case, namely a decision procedure for arithmetic, but the argument, were it valid, would easily generalize to, e.g., the halting problem. It's somewhat long and inevitably technical, so I've made it a notebook entry.
Fortunately for the fate of my immortal soul, after writing down the argument I spotted a fatal error, which can't be fixed save on pain of circularity. At a more minor level, there's an important but very technical bit in the middle which may be right, but would need to be checked very carefully, and which, needless to say, I haven't. There will be a prize for the first reader to correctly identify both these bugs, and another prize for the reader who spots the most mistakes I didn't (not counting typos).
Update, later that night: Ben Wieland points out that the notebook had an embarrassing mix-up between truths and theorems, now fixed. I know better, really I do...
Trackback: Stephen Laniel's Unspecified Bunker
Complexity; Mathematics; Modest Proposals; Philosophy; Enigmas of Chance
Posted at November 17, 2003 19:47 | permanent link