Theory_of_Computation_Lecture_Notes-Abhijat_Vichare.pdf

Theory of Computation Lecture Notes

Theory of Computation

Lecture Notes

Abhijat Vichare

August 2005

Contents

● 1 Introduction

● 2 What is Computation ?

● 3 The λ Calculus

3.1 Conversions:

3.2 The calculus in use

3.3 Few Important Theorems

3.4 Worked Examples

3.5 Exercises

● 4 The theory of Partial Recursive Functions

4.1 Basic Concepts and Definitions

4.2 Important Theorems

4.3 More Issues in Computation Theory

4.4 Worked Examples

4.5 Exercises

● 5 Markov Algorithms

5.1 The Basic Machinery

5.2 Markov Algorithms as Language Acceptors and Recognisers

5.3 Number Theoretic Functions and Markov Algorithms

5.4 A Few Important Theorems

5.5 Worked Examples

5.6 Exercises

● 6 Turing Machines

6.1 On the Path towards Turing Machines

6.2 The Pushdown Stack Memory Machine

6.3 The Turing Machine

6.4 A Few Important Theorems

6.5 Chomsky Hierarchy and Markov Algorithms

6.6 Worked Examples

6.7 Exercises

● 7 An Overview of Related Topics

7.1 Computation Models and Programming Paradigms

7.2 Complexity Theory

● 8 Concluding Remarks

● Bibliography

1 Introduction

http://www.cfdvs.iitb.ac.in/~amv/Computer.Science/courses/theory.of.computation/ (1 of 41) [12/23/2006 1:14:53 PM]

Theory of Computation Lecture Notes

Theory of Computation

Lecture Notes

Abhijat Vichare

August 2005

Contents

● 1 Introduction

● 2 What is Computation ?

● 3 The λ Calculus

3.2 The calculus in use

3.3 Few Important Theorems

3.4 Worked Examples

3.5 Exercises

● 4 The theory of Partial Recursive Functions

4.1 Basic Concepts and Definitions

4.2 Important Theorems

4.3 More Issues in Computation Theory

4.4 Worked Examples

4.5 Exercises

● 5 Markov Algorithms

5.1 The Basic Machinery

5.2 Markov Algorithms as Language Acceptors and Recognisers

5.3 Number Theoretic Functions and Markov Algorithms

5.4 A Few Important Theorems

5.5 Worked Examples

5.6 Exercises

● 6 Turing Machines

6.1 On the Path towards Turing Machines

6.2 The Pushdown Stack Memory Machine

6.3 The Turing Machine

6.4 A Few Important Theorems

6.5 Chomsky Hierarchy and Markov Algorithms

6.6 Worked Examples

6.7 Exercises

● 7 An Overview of Related Topics

7.1 Computation Models and Programming Paradigms

7.2 Complexity Theory

● 8 Concluding Remarks

● Bibliography

1 Introduction

In this module we will concern ourselves with the question:

http://www.cfdvs.iitb.ac.in/~amv/Computer.Science/courses/theory.of.computation/toc.html (1 of 37) [12/23/2006 1:17:43 PM]

3.1 Conversions:

Theory of Computation Lecture Notes

We first look at the reasons why we must ask this question in the context of the studies on Modeling

and Simulation.

We view a model of an event (or a phenomenon) as a ``list'' of the essential features that characterize

it. For instance, to model a traffic jam, we try to identify the essential characteristics of a traffic

jam. Overcrowding is one principal feature of traffic jams. Yet another feature is the lack of any

movement of the vehicles trapped in a jam. To avoid traffic jams we need to study it and develop

solutions perhaps in the form of a few traffic rules that can avoid jams. However, it would not be feasible

to study a jam by actually trying to create it on a road. Either we study jams that occur by

themselves ``naturally'' or we can try to simulate them. The former gives us ``live'' information, but we

have no way of knowing if the information has a ``universal'' applicability - all we know is that it

is applicable to at least one real life situation. The latter approach - simulation - permits us to

experiment with the assumptions and collate information from a number of live observations so that

good general, universal ``principles'' may be inferred. When we infer such principles, we gain knowledge

of the issues that cause a traffic jam and we can then evolve a list of traffic rules that can avoid traffic jams.

To simulate , we need a model of the phenomenon under study. We also need another well known

system which can incorporate the model and ``run'' it. Continuing the traffic jam example, we can create

a simulation using the principles of mechanical engineering (with a few more from other branches

like electrical and chemical engineering thrown in if needed). We could create a sufficient number of

toy vehicles. If our traffic jam model characterizes the vehicles in terms of their speed and size, we

must ensure that our toy vehicles can have varying masses, dimensions and speeds. Our model

might specify a few properties of the road, or the junction - for example the length and width of the

road, the number of roads at the junction etc. A toy mechanical model must be crafted to simulate

the traffic jam!

Naturally, it is required that we be well versed with the principles of mechanical engineering - what it

can do and what it cannot. If road conditions cannot be accurately captured in the mechanical model 1 ,

then the mechanical model would be correct only within a limited range of considerations that

the simulation system - the principles of mechanical engineering, in our example - can capture.

Today, computers are predominantly used as the system to perform simulation. In some cases

usual engineering is still used - for example the test drive labs that car manufacturers use to test new

car designs for, say safety. Since computers form the main system on which models are implemented

for simulation, we need to study computation theory - the basic science of computation. This study gives

us the knowledge of what computers can and cannot do.

2 What is Computation ?

Perhaps it may surprise you, but the idea of computation has emerged from deep investigation into

the foundations of Mathematics. We will, however, motivate ourselves intuitively without going into

the actual Mathematical issues. As a consequence, our approach in this module would be to know

the Mathematical results in theory of Computation without regard to their proofs. We will treat

excursions into the Mathematical foundations for historical perspectives, if necessary. Our definitions

and statements will be rigorous and accurate.

Historically, at the beginning of the 20 century, one of the questions that bothered mathematicians

was about what an algorithm actually is. We informally know an algorithm: a certain sort of a

general method to solve a family of related questions. Or a bit more precisely: a finite sequence of steps

to be performed to reach a desired result. Thus, for instance, we have an addition algorithm of

integers represented in the decimal form: Starting from the least significant place, add the

corresponding digits and carry forward to the next place if needed, to obtain the sum. Note that

an algorithm is a recipe of operations to be performed. It is an appreciation of the process, independent

of the actual objects that it acts upon. It therefore must use the information about the nature (properties)

of the objects rather than the objects themselves. Also, the steps are such that no intelligence is required

- even a machine 2 can do it! Given a pair of numbers to be added, just mechanically perform the steps

in the algorithm to obtain the sum. It is this demand of not requiring any intelligence that makes

computing machines possible. More important: it defines what computation is!

Let me illustrate the idea of an algorithm more sharply. Consider adding two natural numbers 3 .

The process of addition generates a third natural number given a pair of them. A simple way

to mechanically perform addition is to tabulate all the pairs and their sum, i.e. a table of triplets of

natural number with the first two being the numbers to be added and the third their sum. Of course,

this table is infinite and the tabulation process cannot be completed. But for the purposes of mechanical -

i.e. without ``intelligence'' - addition, the tabulation idea can work except for the inability to

``finish'' tabulation. What we would really like to have is some kind of a ``black box machine'' to which

we ``give'' the two numbers to be added, and ``out'' comes their sum. The kind of operations that such

a box would essentially contain is given by the addition algorithm above: for integers represented in

the decimal form, start from the least significant place, add the corresponding digits and carry forward

to the next place if needed, for all the digits, to obtain the sum. Notice that the ``algorithm'' is not limited

by issues like our inability to finish the table. Any natural number, howsoever large, is represented by

a finite number of digits and the algorithm will eventually stop! Further, the algorithm is not

particularly concerned about the pair of numbers that it receives to be processed. For any, and every,

pair of natural numbers it works. The algorithm captures the computation process of addition, while

the tabulation does not . The addition algorithm that we have presented, is however intimately tied to

the representation scheme used to write the natural numbers. Try the algorithm for a

http://www.cfdvs.iitb.ac.in/~amv/Computer.Science/courses/theory.of.computation/toc.html (2 of 37) [12/23/2006 1:17:43 PM]

Theory of Computation Lecture Notes

Roman representation of the natural numbers!

We now have an intuitive feel of what computation seems to be. Since the 1920s Mathematics

has concerned itself with the task of clearly understanding what computation is. Many models have

been developed, and are being developed, that try to sharpen our understanding. In this module we

will concern ourselves with four different approaches to modeling the idea of computation. The

following sections, we will try to intuitively motivate them. Our approach is necessarily introductory and

we leave a lot to be done. The approaches are:

1. The Calculus,

2. The theory of Partial Recursive Functions,

3. Markov Algorithms, and

4. Turing Machines.

3 The Calculus

This is the first systematic attempt to understand Computation. Historically, the issue was what was

meant by an algorithm. A logician, Alonzo Church, created the calculus in order to understand

the nature of an algorithm. To get a feel of the approach, let us consider a very simple ``activity'' that

we perform so routinely that we almost forget it's algorithmic nature - counting.

An algorithm, or synonymously - a computation, would need some object to work upon. Let us call it .

In other words, we need an ability to name an object. The algorithm would transform this object

into something (possibly itself too). This transformation would be the actual ``operational details'' of

the algorithm ``black box''. Let us call the resultant object . That there is some rule that transforms

to is written as: . Note that we concentrate on the process of transforming to , and

we have merely created a notation of expressing a transformation. Observe that this

transformation process itself is another object, and hence can be named! For example, if

the transformation generates the square of the number to which it is applied, then we name

the transformation as: square . We write this as:

. The final ability that an

algorithm needs is that of it's transformation, named being applied on the object named . This

is written as

. Thus when we want to square a natural number , we write it as

An algorithm is characterized by three abilities:

2. Transformation specification, technically known as abstraction , and

3. Transformation application, technically known as application .

These three abilities are technically called as terms.

The addition process example can be used to illustrate the use of the above syntax of calculus

through the following remarks. (To relate better, we name variables with more than one letter

words enclosed in single quotes; each such multi-letter name should be treated as one single symbol!)

1. `add', `x', `y' and `1' are variables (in the calculus sense).

2. is the ``addition process'' of bound variables and . The bound variables

``hold the place'' in the transformation to be performed. They will be replaced by the actual numbers to

be added when the addition process gets ``applied'' to them - See remark . Also the

process specification has been done using the usual laws of arithmetic, hence

on the right

hand side 4 .

3. is the application of the abstraction in remark to the term .

An application means replacing every occurrence of the first bound variable, if any, in the body of the

term be applied (the left term) by the term being applied to (the right term). being the first

bound variable, it's every occurrence in the body

is replaced by due to the application.

This gives us the term: , i.e. a process that can add the value 1 to it's input

as ``signalled'' by the bound variable that ``holds the place'' in the processing.

http://www.cfdvs.iitb.ac.in/~amv/Computer.Science/courses/theory.of.computation/toc.html (3 of 37) [12/23/2006 1:17:43 PM]

1. Object naming; technically the named object is called as a

Theory of Computation Lecture Notes

4. We usually name

as `inc' or '1+'.

3.1 Conversions:

We have acquired the ability to express the essential features of an algorithm. However, it still remains

to capture the effect of the computation that a given algorithmic process embodies. A process

involves replacing one set of symbols corresponding to the input with another set of

symbols corresponding to the output. Symbol replacement is the essence of computing. We now

present the ``manipulation'' rules of the calculus called the conversion rules.

We first establish a notation to express the act of substituting a variable in an expression by

another variable to obtain a new expression as:

( is whose every

is replaced by ). Since the

specifies the binding of a variable in , it follows that

must occur free in . Further, if occurs free in then this state of must be preserved

after substitution - the in and the that would be substituting are different! Hence we

must demand that if is to be used to substitute in then it must not occur free in . And finally,

if occurs bound in then this state of too must be preserved after substitution. We must

therefore have that must not occur bound in . In other words, the variable does not occur

(neither free nor bound) in expression .

The conversions are:

Since a bound variable in a expression is simply a place holder, all that is required is that unique

place holders be used to designate the correct places of each bound variable in the expression. As long

as the uniqueness is preserved, it does not matter what name is actually used to refer to their

respective places 5 . This freedom to associate any name to a bound variable is expressed by the

conversion rule which states the equivalence of expressions whose bound variables have

been merely renamed. The renaming of a bound variable in an expression

to a variable

that does not occur in is the conversion:

conversion: Iff does not occur in ,

As a consequence of conversion, it is possible for us to substitute while avoiding accidental change

in the nature of occurrences. conversion is necessary to maintain the equivalence of the

expressions before and after the substitution.

This is the heart of capturing computation in the calculus style as this conversion expresses the

exact symbol replacement that computation essentially consists of. We observe that an

application represents the action of an abstraction - the computational process - on some ``target''

object. Thus as a result of application, the ``target'' symbol must replace every occurrence of the

bound variable in the abstraction that is being applied on it. This is the conversion rule expressed

using substitution as:

conversion: Iff does not occur in ,

http://www.cfdvs.iitb.ac.in/~amv/Computer.Science/courses/theory.of.computation/toc.html (4 of 37) [12/23/2006 1:17:43 PM]

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: