#
Opinion 125: Now that Alan Turing turned 100-years-old, it is time to
have a Fresh Look at His Seminal Contributions, that did lots of
Good But Also Lots of Harm

## By Doron Zeilberger

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!

Opinions of Doron Zeilberger