Introduction to Theory of Computation

Chapter 1 Introduction

1.1 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?
• 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 Theory.

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ödel, 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.

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 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?

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 of systems.

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 Intelligence.