Automata, Computability, and Complexity illuminates the elegant theoretical underpinnings of computing and brings theory to life by demonstrating its influence on modern hardware and software system design.
Complexity theory
The main question asked in this area is “What makes some problems computationally hard and other problems easy?”
Informally, a problem is called “easy”, if it is efficiently solvable.
Examples of “easy” problems are
(i) sorting a sequence of, say, 1,000,000 numbers,
(ii) searching for a name in a telephone directory, and
(iii) computing is the
fastest way to drive from Ottawa to Miami.
On the other hand, a problem is
called “hard”, if it cannot be solved efficiently, or if we don’t know whether
it can be solved efficiently.
Examples of “hard” problems are
(i) time table
scheduling for all courses at Carleton,
(ii) factoring a 300-digit integer into
its prime factor
(iii) computing a layout for chips in VLSI.
Central Question in Complexity Theory: Classify problems according to their degree of “difficulty”. Give a rigorous proof that
problems that seem to be “hard” are really “hard”.
Computability theory
In the 1930’s, G¨odel, Turing, and Church discovered that some of the fundamental mathematical problems cannot be solved by a “computer”. (This
may sound strange, because computers were invented only in the 1940’s).
An example of such a problem is “Is an arbitrary mathematical statement
true or false?” To attack such a problem, we need formal definitions of the
notions of
- computer
- algorithm
- computation
Central Question in Computability Theory: Classify problems
as being solvable or unsolvable.
Automata theory
Automata Theory deals with definitions and properties of different types of
“computation models”. Examples of such models are:
- Finite Automata. These are used in text processing, compilers, and hardware design.
- Context-Free Grammars. These are used to define programming languages and in Artificial Intelligence.
- Turing Machines. These form a simple abstract model of a “real” computer, such as your PC at home.
