goal of this course is to provide the student with a solid knowledge of
the fundamental concepts and methods of the theory of computation as well
as to outline modern research directions. Three different approaches for
capturing the idea of computing in a formal mathematical way will
be discussed finite state machines, grammars and recursive functions.
At the end of the course students are expected to be able to interpret
relate and apply the basic concepts of the theory of computation to problems
from different areas of computer science.
Apply the algebra of theoretical machines to computing
Possess knowledge of non-determinism in computational
Remove nondeterminism from simple models when it
Understand the basic problems of computability,
decidability and the halting problem as well as the relationships
Apply the concept of a Turing machine to the decidability
problem where possible.
Understand the Church-Turing Thesis and its significance
in computer science.
Have a working knowledge of the Chomsky hierarchy
Relate theoretical computer science topics to programming
languages and other recursively enumerable sets.
H. R. Lewis, C. H. Papadimitriou "Elements of the Theory of Computation"
Prentice Hall, 1981.
J.E. Hopcroft, "Introduction to Automata Theory, Languages and Computations" Addison Wesley, 1979.