THE RABBIT, THE FOX AND THE WOLF: A FABLE

One sunny day a rabbit came out of her hole in the ground to enjoy the weather. The day was so nice that the rabbit became careless, so a fox sneaked up to her and caught her. 

"I am going to eat you for lunch!", said the fox. 

"Wait!", replied the rabbit, "You should at least wait a few days." 

"Oh yeah? Why should I wait?" 

"Well, I am just finishing my Ph.D. thesis." 

"Hah, that's a stupid excuse. What is the title of your thesis anyway?" 

"I am writing my thesis on 'The Superiority of Rabbits over Foxes and Wolves.'" 

"Are you crazy? I should eat you right now! Everybody knows that a fox will always win over a rabbit." 

"Not really, not according to my reserch. If you like, you can come to my hole and read it for yourself. If you are not convinced, you can go ahead and have me for lunch." "You are really crazy!" But since the fox was curious and nothing to lose, it went with the rabbit into its hole. The fox never came back out. 

A few days later, the rabbit was again taking a break from writing and sure enough, a wolf came out of the bushes and was ready to eat her. 

"Wait!", yelled the rabbit,"you cannot eat me right now." 

"And why might that be, you fuzzy appetizer?" 

"I am almost finished writing my Ph.D. thesis on 'The Superiority of Rabbits over Foxes and Wolves." 

The wolf laughed so hard that it almost lost its hold on the rabbit. "Maybe I shouldn't eat you, you really are sick in the head, you might have something contagious," the wolf opined. 

"Come read for yourself, you can eat me after that if you disagree with my conclusions. " So the wolf went to the rabbit's hole and never came out. 

The rabbit finished her thesis and was out celebrating in the lettuce fields. Another rabbit came by and asked, "What's up? You seem to be very happy." 

"Yup, I just finished my dissertation. " 

"Congratulations! What is it about?" 

"It is titled 'The Superiority of Rabbits over Foxes and Wolves" 

"Are you sure? That doesn't sound right." 

"Oh yes, you should come over and read it for yourself." 

So they went together to the rabbit's hole. As they went in, the friend saw a typical graduate student abode, albeit a rather messy one after writing a thesis. The computer with the controversial dissertation was in one corner, on the right there was a pile of fox bones, on the left was a pile of wolf bones, and in the middle was a large, lip-licking lion. 

The moral of the story:

The title of your dissertation doesn't matter. All that matters is who your thesis advisor is.

Travelling Salesman Problem

Travelling Salesman Problem

Compiler Complaint

Compiler Complaint

You Know

The Lament of the Real Programmer :-Sir Roger Needham (Cambridge)

Oh once I could program, the best in the land
I wrote in raw hex with unwavering hand.
My mind's eye could follow all possible paths
But now I can't manage the new-fangled maths

I cut lots of code for unaudited cash
And nobody cared that I rarely did wash
But now I'm burned out and admit with a sigh
That the kids from the High School are better than I

I lasted a while as an old-fashioned hack
Because I could knock out a protocol stack
But the mathmos are here now - they've come pretty far
And there's nothing for me but to prop up the bar!.

A proof that the Halting Problem is undecidable By:- Geoffrey K. Pullum

No general procedure for bug checks succeeds.                                                          Now, I won’t just assert that, I’ll show where it leads: I will prove that although you might work till you drop, you cannot tell if computation will stop.

For imagine we have a procedure called P that for specified input permits you to see whether specified source code, with all of its faults, defines a routine that eventually halts.

You feed in your program, with suitable data, and P gets to work, and a little while later (in finite compute time) correctly infers whether infinite looping behavior occurs.

If there will be no looping, then P prints out ‘Good.’ That means work on this input will halt, as it should. But if it detects an unstoppable loop, then P reports ‘Bad!’ --- which means you’re in the soup.

Well, the truth is that P cannot possibly be, because if you wrote it and gave it to me, I could use it to set up a logical bind that would shatter your reason and scramble your mind.

Here’s the trick that I’ll use -- and it’s simple to do. I’ll define a procedure, which I will call Q, that will use P’s predictions of halting success to stir up a terrible logical mess.

For a specified program, say A, one supplies, the first step of this program called Q I devise is to find out from P what’s the right thing to say of the looping behavior of A run on A.

If P’s answer is ‘Bad!’, Q will suddenly stop. But otherwise, Q will go back to the top, and start off again, looping endlessly back, till the universe dies and turns frozen and black.

And this program called Q wouldn’t stay on the shelf; I would ask it to forecast its run on itself. When it reads its own source code, just what will it do? What’s the looping behavior of Q run on Q?

If P warns of infinite loops, Q will quit; yet P is supposed to speak truly of it! And if Q’s going to quit, then P should say ‘Good.’ Which makes Q start to loop! (P denied that it would.)

No matter how P might perform, Q will scoop it: Q uses P’s output to make P look stupid. Whatever P says, it cannot predict Q: P is right when it’s wrong, and is false when it’s true!

I’ve created a paradox, neat as can be --- and simply by using your putative P. When you posited P you stepped into a snare; Your assumption has led you right into my lair.

So where can this argument possibly go? I don’t have to tell you; I’m sure you must know. A reductio: There cannot possibly be a procedure that acts like the mythical P.

You can never find general mechanical means for predicting the acts of computing machines; it’s something that cannot be done. So we users must find our own bugs. Our computers are losers!

About Theory of Computation

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.

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.