This book introduces the new realm of superrecursive algorithms and the development
of mathematical models for them. Although many still believe that only recursive
algorithms exist and that only some of them are realizable, there are many
situations in which people actually work with superrecursive algorithms. Examples
of models for superrecursive algorithms are abstract automata like inductive Turing
machines as well as computational schemes like limiting recursive functions.
The newly emerging field of the theory of superrecursive algorithms belongs to
both mathematics and computer science. It gives a glimpse into the future of computers,
networks (such as the Internet), and other devices for information interchange,
processing, and production. In addition, superrecursive algorithms provide more adequate
models for modern computers, the Internet, and embedded systems. Consequently,
we hope (and expect) that this theory of superrecursive algorithms will, in
the end, provide new insight and different perspectives on the utilization of computers,
software, and the Internet.
The first goal of this book is to explain how superrecursive algorithms open
new kinds of possibilities for information technology. This is an urgent task. As Papadopoulos
(2002) writes, “If we don’t rethink the way we design computers, if we
don’t find new ways of reasoning about distributed systems, we may find ourselves
eating sand when the next wave hits.” We believe that a theory of superrecursive algorithms
makes it possible to introduce a new paradigm for computation, one that
yields better insight into future functioning of computers and networks. This form of
computation will eclipse the more familiar kinds and will be commercially available
before exotic technologies such as DNA and quantum computing arrive.
Another goal of this book is to explain how mathematics has explicated and evaluated
computational possibilities and its role in extending the boundaries of computation.
As we do this, we will present the theory of algorithms and computation in a
new, more organized structure.