Written: June 23, 2012
Today is the 100th birthday of one of the greatest intellectual giants of all time, Alan Turing, who single-handedly founded computer science, way before computers existed. Well, he did make up the concept of a computer, the famous "Turing machine", and gave a lovely proof (much simpler than the original) of Gödel's Entscheidungsproblem theorem.
But just like Gödel, he missed the point! Neither of them proved that "there exist true yet unprovable statements". Rubbish! Every meaningful statement is either provable (if it is true) or disprovable (if it is false). What they did (meta-)prove, by a Reductio Ad Absurdum clever argument, is that many statements that were believed to be meaningful, are really utterly devoid of meaning. As I have already preached in this sermon, the problem is the fictional (and pernicious!) infinity. In particular, Turing thesis's (recently edited and republished by Andrew Appel in this attractive book (with an insightful introduction by him)), is utter nonsense, talking about "oracles", that lead to lots of beautiful, but fictional and irrelevant work by logicians and theoretical computer scientists.
The very notion of "Turing machine" is flawed, since it assumes "infinite tape". Also the "halting problem" is meaningless, as stated (so it is not surprising that it is "undecidable"). The question "does the program halt" is the same as "does there exist an integer N such that the program halts in less than N steps?", and it is tacitly assumed that N can be anything, i.e. taken over the "infinite" set of positive integers.
The proper definition of a Turing machine should be "with memory up to M", where you are welcome to leave M symbolic, but it is finite (like everything!), and the proper question is "does it halt in less than N steps"?
If we adopt a finitistic viewpoint in computer science (and mathematics!) we will be much better off, and will not waste our time with meaningless questions. Let's start, right now!