1.1 Purpose and motivation
This course is on the Theory of Computation, which tries to answer the
• What are the mathematical properties of computer hardware and software?
• What is a computation and what is an algorithm? Can we give rigorous
mathematical definitions of these notions?
• What are the limitations of computers? Can “everything” be computed? (As we will see, the answer to this question is “no”.)
Purpose of the Theory of Computation:
Develop formal mathematical models of computation that reflect real-world computers.
This field of research was started by mathematicians and logicians in the
1930’s, when they were trying to understand the meaning of a “computation”.
A central question asked was whether all mathematical problems can be
solved in a systematic way. The research that started in those days led to
computers as we know them today.
Nowadays, the Theory of Computation can be divided into the following three areas: Complexity Theory, Computability Theory, and Automata
1.1.1 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 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 factors, and (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”.
1.1.2 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
• algorithm, and
The theoretical models that were proposed in order to understand solvable
and unsolvable problems led to the development of real computers.
Central Question in Computability Theory: Classify problems
as being solvable or unsolvable.
1.1.3 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
• 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.
Central Question in Automata Theory: Do these models have
the same power, or can one model solve more problems than the
1.1.4 This course
In this course, we will study the last two areas in reverse order: We will start
with Automata Theory, followed by Computability Theory. The first area,
Complexity Theory, will be covered in COMP 3804.
Actually, before we start, we will review some mathematical proof techniques. As you may guess, this is a fairly theoretical course, with lots of
definitions, theorems, and proofs. You may guess this course is fun stuff for
math lovers, but boring and irrelevant for others. You guessed it wrong, and
here are the reasons:
1. This course is about the fundamental capabilities and limitations of
computers. These topics form the core of computer science.
2. It is about mathematical properties of computer hardware and software.
3. This theory is very much relevant to practice, for example, in the design
of new programming languages, compilers, string searching, pattern
matching, computer security, artificial intelligence, etc., etc.
4. This course helps you to learn problem solving skills. Theory teaches
you how to think, prove, argue, solve problems, express, and abstract.
5. This theory simplifies the complex computers to an abstract and simple
mathematical model, and helps you to understand them better.
6. This course is about rigorously analyzing capabilities and limitations
Where does this course fit in the Computer Science Curriculum at Carleton University? It is a theory course that is the third part in the series
COMP 1805, COMP 2804, COMP 3803, COMP 3804, and COMP 4804.
This course also widens your understanding of computers and will influence
other courses including Compilers, Programming Languages, and Artificial
Download the pdf file to get all the unit wise notes.
Try to save your valueable time!