Information Technology Reference
In-Depth Information
6
Mr. Turing's amazing machines
Electronic computers are intended to carry out
any definite rule of thumb process which could
have been done by a human operator working in a
disciplined but unintelligent manner.
Alan Turing
1
WARNING: This chapter is more mathematical in character than the rest of the
topic. It may therefore be hard going for some readers, and they are strongly
advised either to skip or skim through this chapter and proceed to the next
chapter. This chapter describes the theoretical basis for much of formal com-
puter science.
Hilbert's challenge
Are there limits to what we can, in principle, compute? If we build a big
enough computer, surely it can compute anything we want it to? Or are there
some questions that computers can never answer, no matter how big and pow-
erful a computer we build. These fundamental questions for computer science
were being addressed long before computers were built!
In the early part of the twentieth century, mathematicians were struggling
to come to terms with many new concepts including the theory of infinite
numbers and the puzzling paradoxes of set theory. The great German mathe-
matician David Hilbert (
B.6.1
) had put forward this challenge to the mathemat-
ics community: put mathematics on a consistent logical foundation. It is now
difficult to imagine, but in the early twentieth century, mathematics was in as
great a turmoil as physics was at that time. In physics, the new theories of rel-
ativity and quantum mechanics were overturning all our classical assumptions
about nature. What was happening in mathematics that could be comparable
to these revolutions in physics?
In the late nineteenth century, mathematics was becoming liberated from
its traditional role in just having application to counting and measurement. In
high school algebra, letters started to be used as symbols for numerical quan-
tities. By the twentieth century, a more abstract view had emerged in which
an “obvious” numerical rule of algebra such as x + y = y + x, was taken to be
just a rule about how symbols could be moved around, and not necessarily
to be interpreted in terms of numbers. Hilbert was one of the leaders of the
formalistic approach to mathematics, which transformed mathematics into a
B.6.1. David Hilbert (1862-1943)
believed that in mathematics all
problems could be solved, provided
we work hard enough. The writing
on his tombstone reads “Wir müssen
wissen, wir werden wissen” - or in
English “We must know, we will
know.”
102
Search WWH ::
Custom Search