Topics
In the first six lectures of this course, we have met two important
classes of languages, namely the regular and the context-free
languages, and the simplest computational devices that
accepted/generated them. We have also seen that both finite automata
and context-free grammars had inherent computational limitations, in
that there are languages that are not context-free, but for which we
can come up with algorithms that accept precisely all the strings in
those languages and no other. This clearly indicates that context-free
grammars are not sufficiently powerful to serve as a general formal
model of algorithms, and indeed they were never meant to be one!
What then is a general model of algorithms? Can every algorithmic problem
be solved? These are fundamental scientific questions that lie at the
heart of computing science, and whose answer sheds light on the
possibilities of computing machines of all kinds. The branch of
science that addresses these questions is called computability
theory, and we shall devote the next three lectures of this course
to a brief introduction to this topic.
We shall see that there are algorithmic 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, 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.
Time and Location
Friday, 1 October, 2004 at 10:15 in A4-106.
Reading Material
-
Chapter 3 (up to page 135) in Sipser's book.
- Pages 218-236 in chapter 9 of D. Harel's book Algorithmics:
The Spirit of Computing. (Optional, but strongly recommended as
an introductory, and above all enjoyable and stimulating, further
reading. These pages will be available for photocopying from the
course folder in due course. Be patient!)
Exercises
Solve exercises 3.2(a)(*), (c)(*) and (e), 3.5(*), 3.8(*),
3.14(*), and 3.15(*) in Sipser's book.
Luca Aceto,
Department of
Computer Science,
Aalborg University.
Last modified: