NP-Completeness for a 9-year-old

I read a lot of blogs; one of them is about computational complexity. I enjoyed this entry; it reminds me a little of the “sorting in real life” activity for kids, where they sort numbers by walking down paths and choosing left or right (i.e. a sorting network). Very cool — more CS for kids!

Posted at 2004-10-08 08:08:21 by Richard • Link to NP-Completeness fo…
Comments, trackbacks.

Disagreeing with John McCarthy

In Paul Graham's ILC 2003 invited talk, he suggests

So if a language is any good, source code ought to be a better way to convey ideas than English prose.

In a footnote, he recollects

At the conference, John McCarthy pointed out that a function to invert a matrix might be better described by writing "inverts a matrix" than by giving the source.

Now, either McCarthy was joking (which is entirely possible), or he's missed the point.

For the sake of argument, I assume the second. He has made the implicit assumption that programming is communication, and that it is analogous to communication with humans — in this case, with a human being who understands about matrices. The problem is that he has assumed the human being's knowledge of matrices, but not the system's.

Consider lists. I could tell a human being, “reverse the list (a, b, c)”. Similarly, I could tell Lisp (reverse '(a b c)). I don't think anyone would argue that the English is a better description.

With the matrices, of course, in a fair comparison one of two situations exists. Either we have both agents understanding matrices, in which case we have “invert the matrix A” and (invert-matrix A), or neither do. In this instance (and taking the much simpler example of matrix transposition instead of inverse), we have

“A matrix is a 2-dimensional arrangement of values. Label the position of each item with two numbers: the first number, i, is its position horizontally; the second, j, its position vertically. One transposes a matrix by switching the positions of every two elements for which the first's i index is equal to the second's j index, and vice versa.”

versus

(defun transpose-matrix (m)
(apply 'mapcar (cons 'list m)))

Of course, there is assumed knowledge on both sides, but I think the point is made — descriptions can only be compared when the equivalent vocabulary is available to both sides. In other words, I think Paul Graham is right, all things considered.

Posted at 2004-10-08 08:05:21 by Richard • Link to Disagreeing with J…
Comments, trackbacks.

Awesome Slashdot fortune

A musical reviewer admitted he always praised the first show of a new theatrical season. "Who am I to stone the first cast?"

Posted at 2004-10-08 05:16:49 by Richard • Link to Awesome Slashdot f…
Comments, trackbacks.