- Luca Aceto (Lecturer)
- Gerd Behrmann (Teaching Assistant)

- Models for the description of algorithms (with special
emphasis on
*Turing Machines*) and their equivalence, - Church-Turing's thesis,
- Unsolvable problems.

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, to appear) by David Harel.

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

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.

- Course description (Postscript file)
*En note om Rice's saetning*(version of 21 October 1997; postscript file) by Hans Hüttel.- Schedule and Contents of Lectures.
(In general, the "spiseseddler" will be posted here a few days before the lectures.)

- 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!
- Turing's World: A book on Turing machines that comes with a program that allows one to design and debug Turing machines.
- Turing Machine simulation in Java.

These are maintained by:

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!)

- 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.
- Bibliographic Database for Computability Theory.
- Stephen Cole Kleene in the Encyclopaedia Britannica.
- Goedel's Incompleteness Theorems in the Encyclopaedia Britannica.
- NP-completeness in the Encyclopaedia Britannica.

- Frequently Asked Questions about Quantum Computation.
- Introductions and Tutorials on Quantum Computation.
- Scientific American "Ask the Experts" on DNA-based computing.
- Publications on DNA based Computers.

Luca Aceto, Department of Mathematics and Computer Science, Aalborg University. Last modified: Fri Dec 3 09:27:59 MET 1999