Information Technology Reference
In-Depth Information
Turing in the late 1930s as a means of exploring a long-standing puzzle
in theoretical mathematics known as the
Entscheidungsproblem
. In order
to facilitate his exploration, Turing invented a new tool, an imaginary
device capable of performing simple mechanical computations. Each
Turing Machine, which consisted of only a long paper tape along with
a mechanism for reading from and writing to that tape, contained a table
of instructions that allowed it to perform a single computation. As a
computing device, the Turing Machine is deceptively simple; as a con-
ceptual abstraction, it is extraordinarily powerful. As it turns out, the
table of instructions for any Turing Machine can be rewritten to contain
the instructions for building any other Turing Machine. The implication,
as articulated in the Church-Turing thesis, is that every Turing Machine
is a Universal Turing Machine, and by extension, every computing
machine is essentially equivalent.
In the real world, the appealingly egalitarian abstractions of the
Church-Turing thesis quickly break down in the face of the temporal
and spatial constraints of the physical universe. To implement even the
simplest computations on an archetypal paper tape-based Turing
Machine, for example, would require an enormous and prohibitive
amount of resources. In fact, the fi gures involved quickly become absurdly
Saganesque: the number of miles of paper tape required would be more
than the total number of atoms in the universe, and the amount of time
required would be more than all of known cosmological history. To the
emerging discipline of theoretical computer scientists, perhaps, none of
these practical realities were particularly signifi cant. But to working
computer engineers and programmers, such constraints were a daily
reality, even in the era of electronic computing. Extracting acceptable
performance and reliability out of the early electronic computers required
an enormous degree of messy tinkering, local knowledge, and idiosyn-
cratic technique. The developing tension between the messy tinkering of
real-world computing and the clean abstractions of academically minded
computer scientists would come to defi ne one of the sharp divides within
the ranks of the larger computing community. The struggle between
theory and practice would become a major challenge for academics and
practitioners alike, and would refl ect itself in the structure of program-
ming languages, professional societies, and academic curricula.
Conventional histories of computer programming tend to confl ate
programming as a vocational activity with computer science as an aca-
demic discipline. In many of these accounts, programming is represented
as a subdiscipline of formal logic and mathematics, and its origins are
