Introduction

Purpose and motivation

This course is on the Theory of Computation, which tries to answer the
following questions:

• What are the mathematical properties of computer hardware and

software?

• mathematical definitions of these notions? What is a computation and

what is an algorithm?

• 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
Theory.
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 Muranga to Nairobi.

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 Muranga University,
(ii) factoring a 300-digit integer into its prime factors

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, Godel, 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, and

• computation.

2|Page
 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.

Purpose and motivation

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.

Central Question in Automata Theory: Do these models have the same

power, or can one model solve more problems than the other?

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.

This is a fairly theoretical course, with lots of definitions, theorems, and proofs. This
course is about the fundamental capabilities and limitations of computers. These
topics form the core of computer science. The course is
1. It is about mathematical properties of computer hardware and software.

3|Page
 2. 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.
3. This course helps you to learn problem solving skills. Theory teaches you how
to think, prove, argue, solve problems, express, and abstract.
4. This theory simplifies the complex computers to an abstract and simple
mathematical model, and helps you to understand them better.

5. This course is about rigorously analyzing capabilities and limitations of systems.

.
This course also widens your understanding of computers and will influence other
courses including Compilers, Programming Languages, and Artificial
Intelligence.

4|Page
 Mathematical preliminaries
Throughout this course, we will assume that you know the following mathematical
concepts:

1. A set is a collection of well-defined objects. Examples are

(i) the set of all Kenya Olympic Gold Medallists,

(ii) the set of all pubs in Muranga, and
(iii) the set of all even natural numbers.

2. The set of natural numbers is N = {1,2,3,...}.

3. The set of integers is Z = {...,−3,−2,−1,0,1,2,3,...}.

4. The set of rational numbers is Q = {m/n : m ∈ Z,n ∈ Z,n 6= 0}.

5. The set of real numbers is denoted by R.

6. If A and B are sets, then A is a subset of B, written as A ⊆ B, if every element of A

is also an element of B. For example, the set of even natural numbers is a subset
of the set of all-natural numbers. Every set every set A is a subset of itself, i.e.,A,
i.e., ∅ ⊆ A. A ⊆ A. The empty set is a subset of

7. If B is a set, then the power set P(B) of B is defined to be the set of all subsets of
B:
P(B) = {A : A ⊆ B}.

Observe that ∅ ∈ P(B) and B ∈ P(B).

8. If A and B are two sets, then

(a) their union is defined as

A ∪ B = {x : x ∈ A or x ∈ B},

5|Page
 (b) their intersection is defined as

A ∩ B = {x : x ∈ A and x ∈ B},

(c) their difference is defined as

A \ B = {x : x ∈ A and x 6∈ B},

(d) the Cartesian product of A and B is defined as

A × B = {(x,y) : x ∈ A and y ∈ B},

(e) the complement of A is defined as

A = {x : x 6∈ A}.

9. A binary relation on two sets A and B is a subset of A × B.

10. A function f from A to B, denoted by f : A →aB∈, is a binary relationa. We will also

sayA, there is exactly

R, having the property that for each element one ordered pair in R, whose first
component is that f(a) = b, or f maps a to b, or the image of a under f is b. The set
A is called the domain of f, and the set

{b ∈ B : there is an a ∈ A with f(a) = b}

is called the range of f.

11. A function f : A →0 inBAis, we haveone-to-onef((aor) 6=injective, there exists an

elementf(a0). The function), if for any two distinctf isa ∈ontoA, elements a and a

6|Page
 (or surjective), if for each element b ∈ B such that f(a) = b; in other words, the
range of f is equal to the set B. A function f is a bijection, if f is both injective and
surjective.

12. A binary relation R ⊆ A × A is an equivalence relation, if it satisfies the following

three conditions:
(a) R is reflexive: For every element in a ∈ A, we have (a,a) ∈ R.

(b) R is symmetric: For all a and b in A, if (a,b) ∈ R, then also (b,a) ∈ R.

(c) R is transitive: For all a, b, and c in A, if (a,b) ∈ R and (b,c) ∈ R, then also (a,c)
∈ R.

13. A graph G = (V,E) is a pair consisting of a set V , whose elements are called
vertices, and a set E, where each element of E is a pair of distinct vertices. The
elements of E are called edges. The figure below shows some well-known
graphs: K5 (the complete graph on five vertices), K3,3 (the complete bipartite
graph on 2 × 3 = 6 vertices), and the Peterson graph.

K5
K3,3 Petersongraph

The degree of a vertex v, denoted by deg(v), is defined to be the number of edges

that are incident on v.
A path in a graph is a sequence of vertices that are connected by edges. A path is
a cycle, if it starts and ends at the same vertex. A simple path is a path without any

7|Page
 repeated vertices. A graph is connected, if there is a path between every pair of
vertices.

14. In the context of strings, an alphabet is a finite set, whose elements are called
symbols. Examples of alphabets are Σ = {0,1} and Σ =
{a,b,c,...,z}.

15. A string over an alphabet Σ is a finite sequence of symbols, where each symbol
is an element of Σ. The length of a string w, denoted by |w|, is the number of
symbols contained in w. The empty string, denoted by

8|Page
 , is the string having length zero. For example, if the alphabet Σ is equal to {0,1}, then
10, 1000, 0, 101, and are strings over Σ, having lengths 2, 4, 1, 3, and 0, respectively.

16. A language is a set of strings.

17. The Boolean values are 1 and 0, that represent true and false, respectively. The basic
Boolean operations include

(a) negation (or NOT), represented by ¬,

(b) conjunction (or AND), represented by ∧, (c) disjunction (or OR),

represented by ∨,

(d) exclusive-or (or XOR), represented by ⊕, (e) equivalence,

represented by ↔ or ⇔, (f) implication, represented by → or

⇒.
¬0 = 1 0∧0=0 0∨0=0 0⊕0=0 0↔0=1 0→0=1
¬1 = 0 0∧1=0 0∨1=1 0⊕1=1 0↔1=0The following
0→1=1
table explains
1∧0=0 1∨0=1 1⊕0=1 1↔0=0 1→0=0
the meanings
1 1=1 1 1=1 1 1=0 1 1=1 1 1 = 1 of these
operations.
NOT AND OR XOR equivalence implication
∧ ∨ ⊕ ↔ →

9|Page