Teaching Theory of Computation

Published on: 2006-8-12

Teaching Theory of Computation

2006-08-12T17:53:00

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.

sanmary

Sun Jan 13 09:22:03 2008

ya,TC ,personally,i found it as "theory of confusion".my teacher has the whole credit for it.

Pramode C.E

Sun Jan 13 10:06:59 2008

`Theory of confusion' - I like that!! The problem is with the way the subject is presented - too much of dry math/logic without appealing to intuition.

Jagadeesh Bhaskar P

Mon May 19 07:21:36 2008

I never used to know what the subject really meant during my engineering days. It was this intrigue, that took me to read more about the subject, trying to follow an intangible ghost. Now it is my biggest ambition to teach (atleast one class) on theory of computation. The history behind: predicting the class of problems that are not computable even before the computers were invented. Thanks to Alan Turing. The philosophy: Is there an algorithm for mind. And if i have a computer with infinite processing power (not exactly but yes) and storage (Turing machines), will it be able to run the algorithm. And if the algorithm is run, will the computer have emotions and consciousness. Which brings to the need for Turing test and Chinese room argument, and so on. Inevitably the teacher should have read beyond the textbooks, to some stuff like GEB by Hofstader, Emperor's New Mind, Shadows of The Mind and so on, which in popular science terms tells what lies beneath. This is exactly what most lack, and which in turn fails to motivate and hold the interest of the students.

Vishnu

Tue Aug 5 15:56:36 2008

Really! ToC is "Theory Of Confusion" No teachers in our university know what is it, and they evaluate our answer sheets by comparing it with text books. So, all students fail! If we really learn "computation", why learn in this useless way?

David

Tue Mar 17 22:44:37 2009

Hey wait, there's a fallacy here... I have a function is assumed to take no arguments or ignore its arguments (stated to be assumed []). I am then to write a function to analyse it and determine if it stops - as yet I haven't written this, and the claim is nobody can. Thus if will_stop is defined and returns either true or false, it is not the function I have yet to write, which I'll call will_really_stop. If it is not defined, then last_try is invalid and will not stop with a correct answer (Dijkstra allows this and suggests that any error is equivalent to an infinite loop/infinte computation, and should in fact be implemented as such in preference to returning some incorrect value. Thus the correct value for will_really_stop is false, because it will not correctly complete and terminate. The original halting problem depended on being able to apply will_stop to any function and any data, and then apply it to itself with itself as data. dP