August 12th, 2006


Teaching Theory of Computation

TC (Theory of Computation) is an integral part of the CS curriculum - but most of it flies above the head of the average student. The reasons are: (a) the subject itself is hard and requires the students to have the ability to think deeply, (b) most of the prescribed text books have a rigorous, mathematical approach which does not appeal to one's intuition. My knowledge of this subject is near to zero, but I have seen lots of material on the web which when combined with the efforts of a good teacher can make it interesting.

As an example, I have just finished reading part of a sample chapter of Friedman and Felleisen's classic The Little Schemer. The author's playfully introduce the halting problem with the help of Scheme code - Scheme's functional style is ideal for expressing such problems. Let's look at the idea in Python!

We wish to write a function will_stop which will check whether a function `f' which it accepts as argument will stop or not; to simplify things, we will assume that `f' will act only on the empty list.

def will_stop(f):
   # body, returns true or false
Now, will_stop(len) should return true because len([]) is zero, ie, len terminates. Let's say we have another function:
def eternity(x): eternity(x)
will_stop(eternity) should return false because `eternity' is never ending (theoretically). Now, let's write one more function:
def last_try(x): return will_stop(last_try) and eternity(x)
Let's see what happens when we try to evaluate last_try([]). Let's say will_stop(last_try) returns false, then `eternity([])' will not be evaluated and last_try([]) terminates and returns false. But wait, our `will_stop' just now reported that last_try will not stop! This must be false. So, let's assume will_stop(last_try) returns true; in that case, eternity([]) will be evaluated and last_try will not terminate, which again contradicts with what will_stop reports! So we have a situation were it is impossible for us to define a function which we can describe precisely!

Once students are presented with the subject matter in this way, the mathematical aspects can be explored more in detail and might even make some sense! Otherwise, it becomes learning by rote for exam's sake.