Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 Computability and Complexity 2002
The goal of this course is to explain and illustrate one of the most
important and fundamental facets of the world of computing --- its
inherent limitations. We shall see that there are problems for which
no algorithmic solution will ever exist, and realizing the
existence of such inherently unsolvable problems has been one of the
main achievements of 20th century mathematics. Roughly speaking, the
subject matter of the theory of computability is the precise
definition of the informal concept of algorithm, and the
characterization of those problems that can (or, perhaps more
intriguingly, cannot) conceivably be solved by means of
algorithms. In the process of developing such a theory, to which the
bulk of the course will be devoted, we shall touch upon topics such
as:
Models for the description of algorithms (with special
emphasis on Turing Machines) and their equivalence,
Church-Turing's thesis,
Unsolvable problems.
The last part of the course will be devoted to a brief introduction to
the theory of computational complexity. In a nutshell, one may say
that, whereas computability theory is concerned with the class of
problems that can or cannot be solved algorithmically, complexity
theory aims at characterizing the problems for which efficient
algorithmic solutions can conceivably be found. The key concept that
we shall touch upon in this part of the course is that of NP-complete problem.
The main textbook for the course is
Introduction to the Theory of Computation by Michael Sipser. The author
maintains a list of errata for the
current edition of this book. Some of the lectures will be based on material
from John C. Martin's book Introduction to Languages and the Theory of Computation, McGraw-Hill. (Copies of the relevant pages will be available for photocopying when necessary.)
Other excellent references are:
H. Lewis, C. Papadimitriou, Elements of the Theory of
Computation (2nd edition), Prentice-Hall, 1998.
N. Jones,
Computability and Complexity from a Programming Perspective,
MIT Press, 1997.
G. Rozenberg, A. Salomaa, Cornerstones of Undecidability,
Prentice-Hall, 1994. (This is a text of a more advanced nature than the others in this list, and mentions many recent results on, and applications of, the theory of computability. It is good reading for the keen student.)
V.J. Rayward-Smith, A first Course in Computability,
Blackwell, 1985.
A. Kfoury, R. Moll, M. Arbib, A Programming Approach to
Computability, Springer-Verlag, 1982.
N. Cutland, Computability, Cambridge University Press, 1980.
J. Hopcroft, J. Ullman, Formal Languages and their Relations to
Automata, Addison-Wesley, 1969
and many more.
As supplementary reading on the science of computing as a whole, I
also strongly recommend the book
Algorithmics: The Spirit of Computing by David
Harel. Of special relevance to this course are chapters 6-9 ibidem.
The Java Computability Toolkit.
The Java Computability Toolkit (JCT) contains a pair of graphical
environments for creating and simulating NFAs, DFAs, and high level
Turing Machines.
Look also here
for a nice Turing Machine simulator written in Java (and documented in
German). (Many thanks to Thomas
Rask Thomsen for providing this one!)
Other Links of Course Related Interest
Some people whose work has had a great impact on the field of Computability Theory:
A seemingly
interesting introductory link to logic, and its
uses in Computer Science and Mathematics. It has a useful glossary,
where you can find explanations of some of the terminology we use in
the course. As an example, see here
for the notions of effective procedure, decidable, and semi-decidable
problems.
Recently there has been a great interest in alternative models of
computation. Prominent amongst these are quantum computing
and DNA computing. Some information on these exciting models
of computation may be obtained from the following links:
This page will be actively modified over the autumn term
1999, and is currently undergoing heavy restructuring. You are invited
to check it regularly during the autumn term. The page is dormant in
the spring term.
Luca Aceto,
Department of Mathematics and
Computer Science,
Aalborg University.
Last modified: Fri Dec 3 09:27:59 MET 1999