On Computable Numbers, with an Application to the Entscheidungsp...
需积分: 0 2 浏览量
2018-11-28
11:17:02
上传
评论 1
收藏 935KB PDF 举报
On Computable Numbers, with an Application to the
Entscheidungsproblem
(Proc. Lond. Math. Soc., ser. 2 vol. 42 (1936–37), pp. 230–265)
– A Correction
(ibid. vol. 43 (1937), pp. 544–546)
Christos Papadimitriou on —
ALAN AND I
During my sad college years, I often dreamed of Alan. At the time I did not know it was Alan
Turing that I was dreaming of, but it was. I was studying a subject that did not excite me (electrical
engineering), in the inflexible educational system of an oppressive society (Greece of the colonels).
I had no access to a proper scientific library. My life as a fledgling scientist was one of frustration,
blind longing, and episodes of false epiphany. A few subjects (systems theory, communication the-
ory), even though they were taught at school in the most mundane way, enabled one to imagine a
courageous intellectual universe in which questions of the most fundamental nature are confronted
rigorously and head on, and I was aching to enter that universe.
I don’t remember when, in which outdated textbook, handed to me by whom, I got my first
glimpse of the Turing machine. I did not get it all at once, but I knew immediately that this abstract
device is an important exemplar of the higher sphere I had been dreaming. I looked up in the
dictionary the verb ‘to ture’ (I really did). I sought more information, every book I opened those
days I opened it on the index page where ‘Turing machine’ should be.
Eventually I did put it all together, how a British mathematician named Alan Turing answered
through his machine the world’s most fundamental question, ‘what can be computed?’ and did so
with amazing rigor, elegance, imagination and economy. But those days I was thinking of the Turing
machine as a singular breakthrough, the end of a story, something of the past. Two years later, in
1973 – after a year in the Greek army that was even bleaker than my tertiary studies – I was fortunate
to find myself at Princeton (Turing’s Princeton, by the way, where I lived for a year in room 2B of
the Graduate College rumored to be Alan’s room 35 years before). At Princeton I was introduced
to the Theory of Computation, the rich and vibrant scientific tradition essentially built on Turing’s
formalism. I remember how grateful I felt that my prayers had been answered, so to speak, and I was
finally entering the realm of my dreams, far more elegant and exciting than I could ever imagine.
And 5 years later, whilst teaching at Harvard with my friend Harry Lewis, we wrote a textbook on
the subject.
But even though my life now revolved around his intellectual heritage, the truth is, I did not
know Alan. I understood next to nothing about the man’s life, personality, and breadth of achieve-
ment. In 1983, 2 years after our textbook was published, I read one of the books that have influenced
me most: Turing’s powerful and definitive biography by Andrew Hodges. Alan became my hero,
a giant and relentless intellect, a fascinating and complex personality, a man of immense accom-
plishment, impact, and tragedy. When, more than a decade later, the second edition of our textbook
13
剩余102页未读，继续阅读
资源评论
