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 FS2: Computability and Complexity
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. We shall also touch upon the important topic of space
complexity, where we classify the difficulty of solving a
computational problem based on a measure of the amount of memory that
it takes to compute the solution in the worst case.
As an alternative, excellent description of this course I strongly
recommend the preface of Computers
Ltd.: What They Really Can't Do (Oxford University
Press) by David
Harel. This lovely little book by one of Computer Science's best
expositors is highly recommended reading. (See the review
of this book in Plus magazine.)
Aims of the Course
At the end of the course, the students will be able to:
Provide mathematical models of algorithms using, e.g.,
Turing machines;
Formulate statements about the computational status of
interesting problems, and provide proofs for them;
Argue about the complexity of computational problems.
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 course assumes knowledge of basic discrete mathematics, such as
the one that you have been using in courses like Algorithms and
Data Structures and Syntax and Semantics. Those of you
who would like to refresh their memory, or who are not confident about
their understanding of the basic mathematics used in this course, are
strongly encouraged to read, e.g., Chapter 0 of Sipser's book
Introduction to the Theory of Computation. As practice makes
perfect, I also recommend that you work out some of exercises to be
found in those references. Try, for example, exercises 0.2--0.5, 0.7,
0.10--0.11 in Sipser's book. Note!
The above exercises are not really part of this course. How many you
attempt to solve depends only upon your level of confidence with the
mathematics that will be used as the course progresses.
Lecture Plan
The course will consist of a series of 15 lectures. The schedule for the lectures
and their location may be found here
in due course. Any variation to the original lecture plan will be
communicated on these pages.
Our working language for the course will be English.
Exercise Classes and Advice on Modus Operandi
As usual, each lecture will have an associated exercise class. The
exercises mentioned on the web page for a lecture should be solved
during the exercise class that precedes the following lecture. For
example, the exercises listed on the web page for lecture 1 should be
solved before lecture 2. There will be no exercise class preceding the
first lecture.
In general, I shall give you more exercises than you might conceivably
be able to solve during one exercise class. The exercises marked with
a star are those that I consider more important for your
understanding. All the exercises will be "doable", and working them
out will greatly increase your understanding of the topics covered in
the course. The best advice I can give you is to work them all out by
yourselves, and to make sure you understand the solutions if the other
members of your group (or me) gave you the solutions on a golden
plate. Above all, don't give up if you cannot find the key to the
solutions right away. Problem solving is often a matter of mental
stamina as much as creativity.
Above all, try to be critical of your solutions to the exercises. You
may not need (some of) the material covered in this course in your
future careers, but having an analytical and critical attitude will
always help you.
For further advice on how to learn this material (and, in fact, the
material in any course) I strongly recommend that you look at the
slides for the talk Psychologists'
tips on how and how not to learn by Wilfrid Hodges. In
particular, try to reflect upon the hints he gives, and ask yourselves
how much you practice what he preaches. You might also wish to read How
to Read Mathematics by Shai Simonson and
Fernando Gouveau --- a collection of useful, down-to-earth tips on how
to read, and learn from, mathematical texts.
Exam
The exam will be individual and oral. Each student will be examined
for at most 20 minutes on one of the topics listed in the exam
prospectus that will be distributed during the last lecture. The topic
will be selected randomly by each student. The student will be
informed of his/her mark (on the standard 13-scale) after the oral
exam. The student can choose to hold the exam in either Danish or
English.
Note!Information on the exam and
the syllabus for the course are now available, as are the slides that will be available at the
exam.
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 at this really cool Turing Machine Simulation developed by the Buena Vista University Java Team! (This applet was written for Sun's Java Cup International contest by the Java Team at Buena Vista University. It won first place in the Education category.)
Turing's World: A book on Turing machines that comes with a program that allows one to design and debug 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.
Pioneers
of Computing, a page where you can find information on the people
that have shaped our science. You may also wish to have a look at the
Virtual Computer History
Museum. (Thanks to Christian E. Kaas for pointing out that my previous link to these pages was no longer in existence.)
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
2002, 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.
Let me know of any error you find in
the course web pages.