The algorithmic solution of problems has always been one of the major
concerns of mathematics. For a long time such solutions were based on an
intuitive notion of algorithm. It is only in this century that
metamathematical problems have led to the intensive search for a precise
and sufficiently general formalization of the notions of computability
and algorithm. In the 1930s, a number of quite different concepts for
this purpose were pro- posed, such as Turing machines, WHILE-programs,
recursive functions, Markov algorithms, and Thue systems. All these
concepts turned out to be equivalent, a fact summarized in Church's
thesis, which says that the resulting definitions form an adequate
formalization of the intuitive notion of computability. This had and
continues to have an enormous effect. First of all, with these notions
it has been possible to prove that various problems are algorithmically
unsolvable. Among of group these undecidable problems are the halting
problem, the word problem theory, the Post correspondence problem, and
Hilbert's tenth problem. Secondly, concepts like Turing machines and
WHILE-programs had a strong influence on the development of the first
computers and programming languages. In the era of digital computers,
the question of finding efficient solutions to algorithmically solvable
problems has become increasingly important. In addition, the fact that
some problems can be solved very efficiently, while others seem to defy
all attempts to find an efficient solution, has called for a deeper
under- standing of the intrinsic computational difficulty of problems.
