|
Schedule
of Topics
Class
Information:
Textbook
Online resources
Our email addresses
Problem sessions
Grading
Evening exams
Website for the book
Errata
for the book
Exams
Academic
Integrity
|
|
Course Description
In this class, we will
develop a single framework in which all kinds of computational problems can
be defined and analysed. The framework is based on the idea of a
language, and problems are defined as the task of determining whether an
input string is a member of some particular language. Thus this area is
often called formal language theory. But a key idea is that all
problems can be described as language recognition tasks so this framework
shouldn't be thought of as limiting. Instead think of it as a simple
mechanism by which problems that may initially appear very different can be
compared and analyzed to see whether there can exist computational solutions
to them at all, and, if there can, what power those solutions must
possess. We will discuss computational models ranging from very simple
(finite state machines) to pushdown automata (with the power to recognize context
free languages, including standard programming languages) to Turing Machines,
which are powerful enough to solve any problem for which a solution exists,
yet simple enough to describe that we can prove theorems about what they can
and cannot do.
Texts
I have written a text book
for this class, Automata, Computability
and Complexity: Theory and Applications. Prentice-Hall, 2008. It should be available at the Coop or
online from Amazon or Barnes and Noble.
There is a website that
goes along with the book. It is
organized into pages that correspond to the chapters of the book. On those pages, you will find links to
many other useful sites.
If you would like another book as a
supplementary text, I recommend Introduction to the Theory of Computation,
Michael Sipser. Brooks/Cole, 1996.
Contact Information
Elaine Rich - ear@cs.utexas.edu
|