A
Chapter 13
Other Models of
Computation
lthough Turing machines are the most general models of computation
we can construct, they are not the only ones. At various times, other
models have been proposed, some of which at first glance seemed to
be radically different from Turing machines. Eventually, however, all
the models were found to be equivalent. Much of the pioneering work
in this area was done in the period between 1930 and 1940 and a number of
mathematicians, A. M. Turing among them, contributed to it. The results that
were found shed light not only on the concept of a mechanical computation, but
on mathematics as a whole.
Turing's work was published in 1936. No commercial computers were
available at that time. In fact, the whole idea had been considered only in a very
peripheral way. Although Turing's ideas eventually became very important in
computer science, his original goal was not to provide a foundation for the study
of digital computers. To understand what Turing was trying to do, we must
briefly look at the state of mathematics at that time.
With the discovery of differential and integral calculus by Newton and
Leibniz in the seventeenth and eighteenth centuries, interest in mathematics
increased and the discipline entered an era of explosive growth. A number of
different areas were studied, and significant advances were made in almost all of
them. By the end of the nineteenth century, the body of mathematical knowledge
had become quite large. Mathematicians also had become sufficiently
sophisticated to recognize that some logical difficulties had arisen that required a
more careful approach. This led to a concern with rigor in reasoning and a
consequent examination of the foundations of mathematical knowledge in the
process. To see why this was necessary, consider what is involved in a typical
proof in just about every book and paper dealing with mathematical subjects. A
Chapter 13
Other Models of
Computation
lthough Turing machines are the most general models of computation
we can construct, they are not the only ones. At various times, other
models have been proposed, some of which at first glance seemed to
be radically different from Turing machines. Eventually, however, all
the models were found to be equivalent. Much of the pioneering work
in this area was done in the period between 1930 and 1940 and a number of
mathematicians, A. M. Turing among them, contributed to it. The results that
were found shed light not only on the concept of a mechanical computation, but
on mathematics as a whole.
Turing's work was published in 1936. No commercial computers were
available at that time. In fact, the whole idea had been considered only in a very
peripheral way. Although Turing's ideas eventually became very important in
computer science, his original goal was not to provide a foundation for the study
of digital computers. To understand what Turing was trying to do, we must
briefly look at the state of mathematics at that time.
With the discovery of differential and integral calculus by Newton and
Leibniz in the seventeenth and eighteenth centuries, interest in mathematics
increased and the discipline entered an era of explosive growth. A number of
different areas were studied, and significant advances were made in almost all of
them. By the end of the nineteenth century, the body of mathematical knowledge
had become quite large. Mathematicians also had become sufficiently
sophisticated to recognize that some logical difficulties had arisen that required a
more careful approach. This led to a concern with rigor in reasoning and a
consequent examination of the foundations of mathematical knowledge in the
process. To see why this was necessary, consider what is involved in a typical
proof in just about every book and paper dealing with mathematical subjects. A