Students
of computer science in usually take a course on Theory of Computation as an
elective some time after they have finished courses on programming, data
structures, discrete mathematical structures (whatever that means), computer
architecture, programming languages and sometimes operating systems as well. Theory
of computation is of course a very broad and deep area, and it is anyone’s
guess what really should be taught in such course. For example, Dexter Kozen’s
text with the same name
suggests that the course should dwell primarily on complexity classes. Most
courses on Theory of Computation in India follow the classic text by Hopcroft and Ullman [1] on formal
languages and automata which was written at a time when parsing, compiling,
code optimization and complexity theory were pursued as frontier areas of
research. As a result, the exposure to automata theory and formal languages was
considered the most important aspect of the theory, later followed by some
exposure to NP-completeness. Moreover the book was written for graduate
students.
More
recently (apparently on the strength of having course web pages on Programming,
Logic, Programming Languages and Complier Design), I have been bombarded by
questions from students and outsiders (some of them managers with computer
science degrees who are willing to pay thousands of dollars if I agreed to sit
in on such a project) regarding the feasibility of designing tools which would
take the programs of their (novice?) programmers and transform them
automatically into the most efficient program possible or the shortest program
possible in some language. I have even been asked why these programs cannot be
proved automatically thus saving the company a small fortune in testing time
and being able to meet stiff deadlines.
Anyway
that’s my story and I am sticking to it.
It is my
feeling that at a time when courses on compilers, formal languages, complexity
theory and automatic verification are usually electives which students tend to
avoid, this has led to a disconnect between a course primarily devoted to
formal languages and automata theory and the bouquet of courses that students
otherwise need to do in a typical computer science curriculum.
Anyway
that’s my story and I am sticking to it.
It is
also my feeling that IIT students (who are numerically quite literate) feel
most comfortable when numbers and computations on numbers form the basis for a
theory of computation. On the other hand courses on theory of computation which
primarily teach automata and formal languages usually completely ignore the
connections between programming and computability theory and scant attention is
paid to the theory of primitive recursive functions and the design of data
structures or programming language features. As a result students who sit
through a course on automata and formal languages and who have no intention of
pursuing either compilers or formal verification or complexity theory, emerge
from the course feeling that the whole course was useless and unconnected to
anything they have learned and anything else they might learn and of no use
whatsoever in their professional life in industry.
Anyway that’s my story and I am sticking to it.
I decided
therefore to make computability theory the primary focus of these lecture notes
and gradually introduce Turing machines, finite automata and formal languages.
I have used the books of Cutland [4] and Martin Davis ([2], [3]) as my primary
sources for these lecture notes. I have tried to introduce the connections
between the theory of computability with other courses such as programming,
functional programming, data structures, discrete mathematical strucutres and
operating systems in as elementary a fashion as possible. It has been a source
of wonder to me that this beautiful material seems to be taught mostly only to
students of pure or applied mathematics or logic rather than to computer
science students. I am sure students of engineering can absorb this material
and appreciate it equally well, especially since it requires little more than
high school mathematics to understand it (though it might require a more maturity
to appreciate it).
Anyway
that’s my story and I am sticking to it.
I have of
course borrowed freely from various sources, but in many cases I have made
significant departures fromt he original material especially as concerns
notation. Not to put too fine a point on it, I believe that my notation though
strange to look at, is an attempt to clean up (mostly for my own understanding)
misleading notation used in various sources.
[1]
Hopcroft J and Ullman J D. Automata, Languages and Computation.
Addison- esley, New York, 1983.
[2] Davis M. Computability and Unsolvability. Dover Publications Inc., New York, 1982.
[3] Davis M and Weyukar E. Computability, Complexity and Languages. Academic Press,New York, 1983.
[4] Cutland N.Computability:An Introduction to Recursive Funt Theory.CUP,Cambridge,Great Britain,1980.
[2] Davis M. Computability and Unsolvability. Dover Publications Inc., New York, 1982.
[3] Davis M and Weyukar E. Computability, Complexity and Languages. Academic Press,New York, 1983.
[4] Cutland N.Computability:An Introduction to Recursive Funt Theory.CUP,Cambridge,Great Britain,1980.
It is a
mystery to me how it has come to be taught as a textbook for an undergraduate
course. I would assume that the same natural processes which brought
Euclid, Descartes and Newton down to school mathematics are responsible for it.
But nevertheless the transition in the case of formal languages and automata
has taken place in less than 15 years while Newton took about 200 years before
being prescribed for high school.
