![](https://csdnimg.cn/release/download_crawler_static/10945256/bg10.jpg)
2
Introduction
true
that
very little
that
is
useful can be said of its physical aspects, such as
its
molecules
and
its
shape;
the
most useful abstractions of a computer are clearly
mathematical,
and
so
the
techniques needed
to
argue
about
them
are necessarily
likewise. Besides, practical computational tasks require
the
ironclad guarantees
that
only
mathematics
provides (we want
our
compilers
to
translate
correctly,
our
application programs
to
eventually terminate, and so on). However,
the
mathematics
employed in
the
theory
of computation
is
rather
different from
the
mathematics
used in
other
applied disciplines.
It
is
generally discrete, in
that
the
emphasis is
not
on real numbers
and
continuous variables,
but
on finite sets
and
sequences.
It
is
based on very
few
and
elementary concepts,
and
draws its
power
and
depth
from
the
careful, patient, extensive, layer-by-Iayer manipula-
tion of these concepts
-just
like the computer. In the first chapter you will
be reminded of these elementary concepts
and
techniques (sets, relations,
and
induction, among others),
and
you will be introduced
to
the
style in which they
are used in
the
theory
of computation.
The
next two chapters,
Chapters
2 and 3, describe certain restricted mod-
els of
computation
capable of performing very specialized string manipulation
tasks, such as telling whether a given string, say
the
word punk, appears in a
given
text,
such as
the
collective works of Shakespeare; or for testing whether
a given string of parentheses
is
properly balanced
--like
0
and
(())O,
but
not
)0.
These restricted computational devices (called finite-state automata
and
pushdown automata, respectively) actually come up in practice as very useful
and
highly optimized components of more general systems such as circuits
and
compilers. Here
they
provide fine warm-up exercises in
our
quest for a formal,
general definition of
an
algorithm. Furthermore, it
is
instructive
to
see how the
power of these devices waxes
and
wanes (or, more often, is preserved) with
the
addition
or
removal of various features, most
notably
of non determinism, an in-
triguing aspect of
computation
which
is
as central as
it
is
(quite paradoxically)
unrealistic.
In
Chapter
4
we
study
general models of algorithms, of which
the
most ba-
sic
is
the
Turing machine,t a
rather
simple extension of
the
string-manipulating
devices of
Chapters
2
and
3 which
turns
out
to
be, surprisingly, a general frame-
t
Named
after Alan
M.
Turing
(1912~1954),
the
brilliant English
mathematician
and
philosopher whose seminal
paper
in 1936
marked
the
beginning
of
the
theory
of
computation
(and
whose image, very appropriately,
adorns
the
cover
of
this
book). Turing also pioneered
the
fields
of
artificial intelligence
and
chess-playing
by
computer,
as well as
that
of
morphogenesis in biology,
and
was
instrumental
in breaking Enigma,
the
German
naval code during World War II. For more
on
his fascinating life
and
times
(and
on
his tragic
end
in
the
hands
of
official cruelty
and
bigotry) see
the
book
Alan
Turing: The Enigma, by
Andrew
Hodges, New
York:
Simon
Schuster, 1983.