Skip to content

Dealing with Intractability and Other Fun Topics: _Computers and Intractability: A Guide to the Theory of NP-Completeness_: The Missing Title from My Advanced Algorithms Course

Back in college, the topic that I spent the bulk of my computer science-related studies in preparing for was the design and analysis of algorithms. More specifically, it was actually my introductory course (Computer Science 365a: Design and Analysis of Algorithms) that required the most preparation:  introduction to computer science, discrete mathematics, meta-logic, data structures and programming techniques, set theory, recursive function theory (also known as “computability theory“), and other topics. Included within “discrete mathematics” was elementary set theory, graph theory, propositional calculus, discrete probability theory, some elementary number theory, mathematical games, and other topics as well.

However, compared to the introductory algorithms course, the following algorithms course (Computer Science 465b: Advanced Algorithms) actually required less following preparation, and was in fact much less overall work. There were only four problem sets (one of which, however, was so difficult that I stayed up all night thinking about all three problems and was unable to solve any of them), and most of the reading involved relatively short research monographs.

As a result, the advanced algorithms course stuck out much less in my memory, and until very recently, I was unable to remember the title of one famous book that I had remembered very well at the time, but which I did not use too often, yet still wanted to recommend as a class to those who are interested in studying algorithms.

Recently, however, in reviewing Rice’s Theorem, I was finally able to remember the title: Computers and Intractability: A Guide to the Theory of NP-Completeness, by Michael Garey and David S. Johnson. The book is reportedly the first title ever written on the theory of NP-completeness and computational intractability, and was relatively easy to read for the subject material.

In the opening, the authors give a somewhat humorous story of a person who is in the predicament of having been asked to come up with an algorithm to solve a problem, but who is unable to solve it. What does he do to keep his job? Well, he explains to his boss, “I can’t find an efficient algorithm, but neither can all these famous people.” The book explains that this is the fundamental motivation for proving that a problem is NP-complete (see below for an explanation of this term): that is, that if a problem can be shown to belong to the class of NP-complete problems, then it is equivalent to an entire class of other problems for which no polynomial-time (i.e., efficient) solution has yet been discovered, and hence the problem is unlikely to be solved easily.

Informally, a problem is NP-complete if and only if it satisfies the following two criteria:

1) It belongs to NP (the class of decision problems that can be solved on a non-deterministic Turing machine in polynomial time), and

2) it is NP-hard (that is, it is at least as hard as the hardest problems in NP).

More informally, a problem is NP-complete if and only if:

1) It is possible to verify a yes-answer efficiently, and

2) any of the other NP-hard problems can be shown to be equivalent to it (via an efficient (i.e., polynomial-time) conversion of the inputs).

What is neat about the class of NP-complete (a.k.a. “NPC”) problems is that although they may all seem different, they are in fact equivalent in the sense that if any one of them can be shown to be solvable quickly (i.e., in polynomial time), then so can the rest.

What this means for the working programmer is that if the boss gives the programmer an unreasonable problem to be solved quickly using a computer program, but he/she is able to show that the problem is NP-complete, then the programmer can just tell the boss, “Well, I wasn’t able to write a program to solve the problem quickly, but neither were a lot of other researchers who also tried to solve the same kind of problem, so no matter who you ask, you are very likely to get the same answer.”  In this case, the boss is unlikely to fire the programmer.

One useful aspect of this title is that it includes an appendix with a compendium of NP-complete problems.  By reducing any of these problems to the problem to be solved, one can show that the problem is NP-complete, and hence, unlikely to be solved quickly by any algorithm implemented on any computer program anytime soon.


Virtually Un-Squeaking: The Paradoxical Link Between Exploring Virtual Worlds, But Studying Haskell and Scheme Instead of Squeak

For the past year and a half or so, I have, on and off, attempted to study Squeak in order to learn how to write in Open Cobalt for the eventual purpose of writing my own virtual world, but for some reason, every time that I start to learn Squeak, I have felt vaguely uncomfortable in working in an object-oriented world, and have soon returned to the functional worlds of Haskell and Scheme.

At first, I thought that the reason had to do with my exposure to the functional programming paradigm, and even once made a paradigm shift. However, despite the paradigm shift, I still gradually returned to Haskell and Scheme.

Just now, after watching part of a talk by Rich Hickey, entitled “Clojure for Lisp Programmers Part 1,” I think that I may have discovered at least part of the real reason for this vague preference. During the talk (from 0:18:47 to 0:18:51 on the video), Hickey offhandedly mentioned, “I’m sort of a Common Lisp guy. I’m not a Scheme guy.”

This comment started me on a train of thought about what I felt about the differences in the styles of programming in Common Lisp vs. Scheme, and how these related to the differences between Clojure and Haskell, and eventually to the differences between Squeak and Haskell as well.

Granted, Common Lisp and Scheme have many similarities: They both use S-expressions in their syntax. They are both based on Alonzo Church‘s lambda calculus. They are both ultimately descended from the Lisp programming language invented by John McCarthy in 1958 at MIT. They are both dynamically typed. In addition, they both use lexical scoping for variables.

However, Common Lisp and Scheme are significantly different dialects of Lisp. Firstly, Scheme is a Lisp-1 dialect, whereas Common Lisp is a Lisp-2 dialect. (The difference between the two is that Lisp-1 dialects share a single namespace for functions and values, whereas Lisp-2 dialects have different namespaces for the two. For a technical explanation of this difference, see the paper “Technical Issues of Separation in Function Cells and Value Cells,” by Richard P. Gabriel and Kent M. Pitman, which appeared in the journal Lisp and Symbolic Computation, Volume 1, No. 1, June 1988, on pages 81-101.) Secondly, Scheme supports tail call optimization and first-class continuations and places a relatively heavy emphasis on recursion, whereas Common Lisp supports more special-purpose iterative looping constructs and has more standard common libraries. However, Common Lisp has no way of evolving, whereas Scheme has an RnRS (“Revised^n Report on [the Algorithmic Language] Scheme”) standardization process.

In particular, the emphasis on special-purpose constructs and standard libraries has a tendency to give many books on Common Lisp a more practical flavor, whereas the emphasis on tail call optimization, continuations, and recursion tends to give many texts on Scheme a more academic or theoretical flavor.

One of my mathematics professors in college once said, “Mathematicians don’t care about the real world.” Aside from whether this is true or not, this statement was actually one of my main reasons for switching from disliking mathematics to enjoying it: I myself don’t really care about the real world. When in college, I enjoyed studying algorithms, programming language theory, haiku poetry, and epic poetry, but disliked economics and social sciences. In my spare time, I enjoyed virtual reality environments, fantasy, and science fiction, but disliked business and generally anything related to monotonous social interaction or money. In short, unless a topic was related to some kind of theory, fantasy, or hypothesis, I wasn’t very interested.

This goes back to Haskell vs. Clojure. Being more of a writer than a programmer, I tend to enjoy discussion about programming language theory. While I have participated on both the Clojure Google group and the Haskell-Cafe mailing list, I have noticed that the latter has a much higher proportion of discussion focusing on relatively theoretical topics, such as semantics and category theory. I think that this, rather than differences between the languages per se, is one of the main reasons that I subconsciously prefer discussing Haskell to discussing Clojure.

This, in turn, goes back to Haskell vs. Squeak. Paradoxically, although it is the combination of my interest in experiencing virtual reality environments and the role of Squeak as the basis of such virtual reality development tools as Croquet and Open Cobalt that first brought me to Squeak, it is precisely my interest in the theoretical and fictional which also turns me away from Squeak and toward Haskell. Most of the discussions on the squeak-dev mailing list tend to be of a practical nature, concerning specific issues with using Squeak. However, I tend to be turned off by relatively mundane discussions. I’d much rather discuss, say, the philosophical basis of Squeak in Richard DawkinsThe Selfish Gene than, say, how to get Squeak to output sound. However, such discussions are relatively few and far between in Squeak discussion-land.

On the Haskell-Cafe, however, it is very common to read discussions about why, say, monads are like burritos. Such discussions remind me of finding the result of (cons ‘peanut ‘(butter and jelly)) on page 7 of The Little Schemer. It is common to find discussions of food related to programming language constructs in documents on both Haskell and Scheme. (Virtual) food is fun. Programming by itself can become monotonous after a while, but programming about food helps keep the doldrums away.

Speaking about (virtual) food, time to get a Rolanberry Pie for my avatar. Now if only my avatar could then program in virtual Haskell or virtual Scheme about virtual monad-burritoes and virtual ‘(peanut butter and jelly)….

ANN: Twitter Account

As of Sunday, April 18, 2010, those of you who are interested may now read Benjamin L. Russell (DekuDekuplex) on Twitter.  There, since each post is limited to 140 characters, I plan to jot down frequent notes on anything interesting I discover.  Feel free to write to me there as well!

While setting up my account there, since I wasn’t satisfied with any of the default themes, I searched and managed to find some exquisite fantasy-theme backgrounds at  For my current theme, I have chosen Blacklight Fantasy, which reminds me of fractals.  What do you think of it?

ANN: Theme changed from Rubric to Titan.

This is an announcement that the theme for this blog has just been tentatively changed from the previous Rubric theme to a new theme, Titan, just announced on March 9, 2010.

Apparent advantages:

* The color scheme is less harsh on the eyes.

* The width is narrower, and hence easier to scan.

* An “About” page is now visible.

* A list of links is now visible.

* The overall look is cleaner.

Apparent disadvantages:

* The titles of recommended publications are no longer visible.

* Long lines must now be scrolled horizontally.

* My trademark logo, the blue butterfly, is no longer visible.

Please let me know what you think of this new theme by either posting a comment or filling out the pop-up poll.  If you have any other suggestions for themes, please post your suggestions as comments, either here or in the poll, as well.

An Algorithm for Algorithms: One Student’s Quest to Pass a Course in the Design & Analysis of Algorithms, and a Poem Upon Reflection

[The material in the following post was quoted, slightly edited for corrections and hyperlinking of titles and terms, and expanded from a personal message that I had sent to one student in an introductory algorithms course who had asked how I had managed to pass a similar course in college.]

The first time I took “Computer Science 365a: Design and Analysis of Algorithms” at Yale University in circa 1991 (the suffix ‘a’ indicates a fall semster course, while ‘b’ indicates a spring semester course), I didn’t actually take it for credit, but happened to be on a Leave of Absence while present on campus, and audited the course, instead.  Fortunately, the people in the Department of Computer Science didn’t know that I was on a Leave of Absence, and I was able to take a dry run of the course, so to speak.

The reason that I did this was that I had previously had great difficulty in conquering a prerequisite course in discrete mathematics, “Computer Science 202a:  Mathematical Tools for Computer Science,” in fall of 1990, which had covered various topics, some of which were easy, and some of which were painful.  I found axiomatic set theory and graph theory relatively easy, propositional calculus tedious but not terribly difficult, number theory interesting, but discrete probability theory painful, and, in particular, linear algebra, taught at the fast pace early in the morning at 8:30 AM when I was extremely sleepy and tired, unmanageable.  The whole point of the entire course was to teach students to write proofs, and almost every problem of every problem set required writing a proof of some kind, most proofs being based on mathematical induction.

I eventually dropped this course for credit, but continued remaining in class until the end of the semester so that I would know what to expect next time.  Then I audited this course at the same time as auditing CS 365a the next year, and was able to pass all the problem sets and examinations.  (Later, I somehow managed to convince the Department of Computer Science to exempt me from taking the course again, since I had essentially successfully completed it once.)

Of all the courses that I was required to take in college, the algorithms course required by far the most preparation, and essentially dominated my life for almost the entire period between fall 1991 and fall 1993, when I eventually managed to pass it.  The textbook used was Introduction to Algorithms (First Edition), by Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest.  (The first and second editions of the book contain substantially significant content, so be sure to distinguish between them.  There is even a third edition, just published on September 30, 2009, Introduction to Algorithms, Third Edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, which reportedly is significantly easier to read.)

(My roommate at the time, Scott P. Horne, who at first was himself pursuing the major in Computer Science (he eventually switched to Chinese Literature, even though he was far more proficient in both mathematics and programming than I, because he claimed to have gotten “bored” with the major in Computer Science), once claimed that it would take me “seven years” to complete that course; I managed to do it in about two and a half years, but only after countless nights of little or no sleep, and two head-splitting migraine headaches after working on mathematical problem sets (one on discrete probability theory in the CS 202a course, and the other on context-free grammars in a later course, “Computer Science 366b:  Models of Computation,” on automata theory and formal languages, which unfortunately I didn’t pass while auditing, but which provided much practice in writing of formal proofs, and which still seemed less work (but more abstract work) than CS 365a, and boosted my confidence in one day eventually being able to pass CS 365a).  (I also once overextended my stamina during an open-book day-long examination in a course in first-order logic, which happened to be in the Department of Philosophy, but required writing proofs that spanned several pages per proof; although I didn’t get a headache at the time, my body broke down and felt poisoned within from accumulation of stress, and the University Health Services (colloquially known by the acronym “DUH,” from its previous title of “Department of University Health,” which changed about twenty years ago) required me to have an enema.))

Conquering the algorithms course required first carrying out the following steps beforehand:

1.  Conquering mathematics phobia.

2.  Reviewing algebra and becoming proficient at writing mathematical proofs, including mathematical notation.

3.  Finding a way to study mathematics without incurring too much stress.

Step 3 above implied the following sub-step, which automatically solved Step 3:

3a.  Finding a way to discover fun in mathematics.

In order to conquer Step 1 above, I managed to enlist the assistance of an undergraduate mathematics student, Andrew Barnes, who agreed to tutor me once a week for about an hour per lesson gratis during the summer of 1991.  He gave me what he referred to as tutoring in “elementary mathematics at an advanced level,” by which he meant that although the tutoring started out from axiomatic set theory and did not assume any background in mathematics above high school level algebra, most problems were of a theoretical nature, and focused on writing proofs of lemmas and theorems, rather than just problem-solving.

By the end of that summer, I was sufficiently prepared to take “Mathematics 270a:  Set Theory,” which was a course in axiomatic set theory in the Department of Mathematics which required writing many proofs of theorems.  To my surprise, while I found that course not difficult and even fun, there was another undergraduate student in the course who was majoring in Electrical Engineering who had more background than me in mathematical problem-solving but much less in proofs, who failed the mid-term course because of an inability to write proofs of theorems, and who subsequently dropped the course.  It was at this point that I realized that maybe I wasn’t quite so stupid in mathematics as I had believed that I was, and that with sufficient effort and persistence, I may yet have some glimmer of eventually passing even the algorithms course.

Related to Steps 3 and 3a, and related to the above-mentioned issue, there were also four books which were of monumental importance:

i.  Naive Set Theory (Undergraduate Texts in Mathematics), by Paul R. Halmos

ii.  Elements of the Theory of Computation (Prentice-Hall software series) (First Edition), by Harry R. Lewis and Christopher Papadimitriou
This textbook was recommended to me by a former student in the Computer Science and Mathematics major, Robert Kissel, who had also been my supervisor at CADWARE, a software company in New Haven, Connecticut, in 1992, at where I had worked as a part-time English-Japanese technical translator.  He then recommended that I ask Dana Angluin, a researcher at the Department of Computer Science at Yale University and wife of Stanley C. Eisenstadt (the professor at the same department who later taught my much-feared “Computer Science 323a:  Introduction to Systems Programming” course in fall of 1993, which I almost didn’t pass).  Ms. Angluin had the opposite personality of the stern Professor Eisenstadt who gave out so much homework that students had very little time to do anything but work on his problems sets, and who gave very few hints in class, out of a concern not to “bore students out of [their] skull[s] by ‘spoon-feeding’ them; instead, Ms. Angluin was one of the kindest and most helpful people whom I had ever met in the department.  She agreed to give me a short tutorial on that book once a week, which helped me in understanding such concepts as diagonalization, finite-state automata, Turing machines, and various models of computation.  This book is extremely thorough, rigorous, and abstract; although I myself enjoyed this book very much (partly because I did not need to complete any problems sets based on it), students tend either to love it or hate it, depending on how abstract their thinking.

iii.  Introduction to Set Theory (Pure and Applied Mathematics) (also used as the textbook for Mathematics 270a), by Karel Hrbacek and Thomas Jech (currently, there is an updated edition, Introduction to Set Theory, Third Edition, Revised and Expanded (Pure and Applied Mathematics), by the same authors)

iv.  Compared to What?: An Introduction to the Analysis of Algorithms (Principles of Computer Science Series) (used as a supplementary textbook when I finally actually passed the algorithms course, CS 365a, in fall of 1993), by Gregory J. E. Rawlins
This was the book on algorithms that I enjoyed reading the most by far.  Unlike Introduction to Algorithms, this book treated each algorithm by starting out with a problem which had not yet been solved, and leading up to how the solution was discovered.  This approach had the advantage of not intimidating the reader by presenting each solution as if it had been arrived at by a genius by magic out of thin air, but instead showing that each algorithm, far from being a magical artifact that had been spontaneously and instantaneously conceived of by such a genius, was in fact only the result of a series of stepwise refinements that any layperson of sufficiently mathematical maturity could have arrived at with sufficient thought.  The importance of this point cannot be belabored:  One reason that at least some students, myself included, at first have difficulty in approaching the subject of algorithms is that they do not understand how the solutions are arrived at, and jump to the conclusion that they somehow require a person of unusual mathematical ingenuity to come up with, and that such algorithms are either arrived at almost instantaneously by geniuses, or never arrived at by almost everyone else.  This is simply not true.  While other books tend to mask the process of thought required to arrive at the solutions, this book covers this area in great detail, while also adding an appealing cover and a number of quotes from Alice’s Adventures in Wonderland to give invoke the atmosphere of that story.  (I also covered my copy of the book with a kaleidoscopic book cover from Peacock Paper Products (a company which doesn’t seem to exist anymore) to enhance this effect.)

Another book that I personally found very helpful in establishing self-confidence in mathematics, but which was irrelevant to the subject area of algorithms, and which may be irrelevant in your case (depending on one’s mathematical background and area(s) of expertise) was a book on calculus which was one of the very few on that subject that I found fun to read.  At the time, I had felt extremely uncomfortable with calculus because of a bad experience that I had had in my first year in college, when somebody had stolen my calculus textbook and my class notes as they were left in the law school library when I went to visit my economics professor just after mid-term when I was already down to three classes from having dropped introductory French; if I then either dropped or didn’t pass any more courses, I would have flunked straight out of college completely.  The book that finally caused me to regain confidence in this subject area was the following:

v.  A First Course in Calculus (Undergraduate Texts in Mathematics) (also used as the textbook for my summer courses in calculus in 1990), by Serge Lang
Be forewarned:  The subject area of this book is completely irrelevant to algorithms.  The only purpose of this book was to reestablish confidence in my ability to do mathematics in general and calculus in particular after the above-mentioned incident.  However, this book actually was interesting to read, because, if I remember correctly, it showed me how to appreciate, among other aspects, beauty in mathematics; in particular, it demonstrated elegant solutions to problems as opposed to ugly solutions.  Although the material itself was elementary, the exposition was eloquent, and the proofs were well-written.  The treatment was very user-friendly, and the author even was able to inject humor at one point.  Reading this book made me feel that there was a live human being writing it who understood the importance of eloquence in writing and elegance in treatment in describing mathematics, rather than simply beating every definition, lemma, and theorem into the logical ground by presenting it in strict logical order, regardless of difficulty level.  With this book, I did not constantly need to skip around the book or to refer to other books to read it, because every point followed directly in a reader-friendly manner from the preceding points.  In addition, the instructor, Jay Jorgensen, of the Department of Mathematics, was very helpful, and had the habit of repeating important points twice, thus making them easier to remember (he once explained that the real reason that he did this was that the course was taught at 10 AM, after he had pulled an all-nighter in doing his mathematics research every night, and that he was simply too sleepy to be able to think of something new to say for every single sentence).

Also related to Steps 3 and 3a were a number of other courses and their textbooks that I also studied in the Department of Mathematics, which I found at least tangentially related to algorithms:

A.  Course Title:  Mathematics 456b:  Recursive Function Theory
Professor:  Ron Sigal
Textbook Title:  [first edition of the following title] Computability, Complexity, and Languages, Second Edition: Fundamentals of Theoretical Computer Science (Computer Science and Scientific Computing), by Martin Davis, Ron Sigal, and Elaine J. Weyuker
This is the second edition of the textbook for the course in this topic taught by Ron Sigal, one of the authors of this book; I used the first edition of this book (for which I cannot seem to find an online reference at the moment).  This book provides a good background in elementary computability theory, which is somewhat related to complexity theory, which is the field of algorithms.

B.  Course Title:  Mathematics 800 (a graduate-level course):  Recursion Equations [domain theory]
Professor:  Ron Sigal
Textbook Title:  <none> (we used class notes for the above-mentioned book for the course in Recursive Function Theory, prepared by Ron Sigal)
This course discussed domain theory, including partial orderings and complete partial orderings (CPO’s), and was a sequel to above-mentioned course in Recursive Function Theory.

C.  Course Title:  Computer Science 430b:  Formal Semantics
Professor:  Paul Hudak
Textbook Title:  Semantics of Programming Languages: Structures and Techniques (Foundations of Computing), by Carl A. Gunter
This was one of the few courses in the major in Computer Science which I actually found to be fun.  The topic was the lambda calculus, the theoretical basis of Scheme.  Professor Hudak’s exposition was very lucid and understandable.  I later audited another of his courses, Computer Science 201a:  Introduction to Computer Science, after completing the major and graduating, in fall of 1993 (if I remember correctly), just to have an opportunity to program in Scheme.  The mid-term project for that course, Schemetris, in which students were each paired with a partner and required to use Scheme graphics libraries provided by the instructor to build a Scheme version of Tetris, greatly increased my confidence in being able to program in Scheme, because my partner chiefly told me which functions to write while I did most of the actual coding, and we got the project done after three days of nearly constant work (during this period, I only slept between about 6 PM and 10 PM every evening, and then pulled an all-nighter afterwards).  Additionally, the TA for that course also commented that one solution which I wrote for one of the problems was much more elegant than the solution arrived at by the TA himself.  Professor Hudak’s influence at that time is partially responsible for my current interest in the functional programming language Haskell, of which he was one of the architects.

I also took some courses and read their required textbooks in the Department of Philosophy taught by Professor Patricia (“Patty”) Blanchette on first-order logic and the logic of Gottlob Frege.  However, their exact course titles and their related textbooks do not spring to my mind at the moment.  While they were helpful in providing practice in logical reasoning and in writing formal proofs, they were not so crucial to my preparation for algorithms as the others; nevertheless, I would suggest taking a course in first-order philosophical logic if you have time.  At least this experience provides an interesting background side story to mathematical logic; in my case, it opened the avenue of philosophy as a hobby, and lead to my reading other books in philosophical logic and related topics, especially by Bertrand Russell.

Finally, related to Step 2 above, I went to the local library at the Department of Mathematics and borrowed an old hardcover book with a brown cover, whose title I don’t remember, published sometime in the 1960’s (if I remember correctly), which contained extremely detailed explanations of the rules of elementary high school algebra and dozens of mini exercises in high school algebra at as elementary a level as the FOIL rule.  Then I went home and practiced with this book for about an hour a day (I couldn’t work with it any longer than that because I would get tired, bored, and sleepy after that time.)  The title and authors of this book did not stick in my memory because I didn’t enjoy working with this book; I just happened to come across it as the least-bad solution that I could find from searching through most of that section of that library to find a book that would give me extensive practice in high-school level algebra, which I had practiced before matriculation, but mostly forgotten out of lack of practice.  One can probably find many other far more interesting books if one looks hard enough.  The most important point about this book was that it was very old and came from a generation of teachers who believed that this area of mathematics was best taught by lots of rote practice; while I found this method extremely boring, the amount of practice did work in my case.

Additionally, to become proficient at mathematical notation, I practiced writing various mathematical symbols which could be easily confused with other writing symbols.  In particular, I wanted to be absolutely certain that I could distinguish between the uppercase letter ‘I,’ the lowercase letter ‘l,’ and the numeral ‘1’; the lowercase letter ‘o,’ the uppercase letter ‘O,’ the numeral ‘0,’ and the uppercase Greek “theta” letter; the lowercase ‘a’ letter and the Greek-lowercase “alpha” letter; the uppercase ‘N’ letter (used to represent a constant integer) and the symbol ‘N’ (used to represent the set of natural numbers); ‘N(sub-0)’ (where ‘N’ represented a constant integer), ‘N(sub-0)’ (where N represented the set of natural numbers), and the Hebrew symbol aleph-null (used to represent the cardinality of the set of natural numbers in set theory); the lowercase ‘x’ letter, the non-mathematical multiplication symbol ‘x,’ and a small closing parenthesis ‘)’ followed without a space by a small opening parenthesis ‘(‘; the ‘.’ symbol and the mathematical multiplication “dot” symbol (only slightly raised); and the uppercase ‘C’ letter and a left-parenthesis ‘(‘ symbol.

For example, I wanted to be able quickly to distinguish between the following one-line lists of expressions:

C) alpha dot x. (l(sub-I) – I(sub-l))(sub-1) =? o.0.O.N (where ‘N’ represents the set of natural numbers)


() a . )(. (I(sub-l) – l(sub-I))(sub-l) =? theta(O.0.o.N (where ‘N’ represents a constant integer))

(Try writing both lines out quickly as if following a crazed, sleepy, and absent-minded mathematics or computer science theory professor with sloppy handwriting in the middle of a rushed class towards the end of a crucial proof which is guaranteed to appear on the next examination.)

Therefore, I set some time aside to practice writing each letter of the Greek alphabet in both uppercase and lowercase, and to establish my own typeface rules to distinguish carefully between the above letters:

The uppercase letter ‘I’ must have serifs on both vertical ends; the lowercase letter ‘l’ must be written in a cursive font; the numeral ‘1’ must be written such that the upper end is written starting slightly below the top end of the numeral and then springing immediately back all the way to the baseline.

The lowercase ‘o’ letter must be written small, the uppercase ‘O’ letter must be written large and never crossed out with a single line, the numeral ‘0’ must always be crossed out with a single line proceeding out of both sides, and the uppercase Greek “theta” letter must always be crossed out with a single line proceeding out of only the right side.

The lowercase Greek “alpha” letter must have both serifs on the right side pointing slightly upwards and slightly downwards, respectively, both toward the right; the lowercase ‘a’ letter must have a single serif on the lower-right corner pointing straight down.

The uppercase letter ‘N’ (used to represent a constant integer) must be written as a plain uppercase letter ‘N’; the special symbol ‘N’ (used to represent the set of natural numbers) must have a double-line instead of a single-line for its left side.

‘N(sub-0)’ (where ‘N’ represents a constant integer) must be written with a plain uppercase letter ‘N’; ‘N(sub-0)’ (where N represents the set of natural numbers) must be written such that the ‘N’ symbol comprises a double-line instead of a single-line for its left side; the Hebrew symbol aleph-null (used to represent the cardinality of the set of natural numbers in set theory) must be written such that it has a pronounced diagonal line jutting out from both ends, with relatively smaller vertical lines extending on mutually opposing sides from this diagonal line from inside both end points.

The lowercase ‘x’ must be written as a horizontally inverted lowercase ‘c’ letter joined to an immediately following small ‘c’ letter (alternatively, it can be written as an extended diagonal line extending from the upper-left corner to the lower-right corner, intersected by a relatively small perpendicular intersecting line extending from the upper-right corner to the lower-left corner); the non-mathematical multiplication symbol ‘x’ is written as a regular lowercase ‘x’ letter, but in a smaller size; and a small closing parenthesis ‘)’ followed without a space by a small opening parenthesis ‘(‘ is written such that both parentheses are relatively obtusely curved (i.e., lightly curved) compared to a horizontally inverted lowercase ‘c’ letter followed without a space by a lowercase ‘c’ letter.

The ‘.’ symbol is always written such that the symbol intersects the baseline; the mathematical multiplication “dot” symbol (only slightly raised) is always written such that the symbol is written slightly above the baseline.

The uppercase letter ‘C’ is always written such that the right ends of the letter are curved sharply to the right; a left-parenthesis symbol ‘(‘ is always written such that the ends of the symbol are relatively softly curved to the right.

Finally, in fall of 1993, I took CS 365a.  I performed acceptably on the problem sets, and although I somehow still failed the mid-term exam (an incident over which the professor, Michael J. Fischer, was very upset), I passed the final and the course.  Finally, “the CS 365 experience” (as one of the graduate TA’s termed it) was over (this person must have known that it was a special experience, since nobody else had ever referred to “the CS xyz experience,” where x, y, and z were any other integers)!  I breathed a long sigh of relief, happy that nothing else of comparative significance in challenge stood in the way to completing the Computer Science major.

My preparation for this course did come at high cost, however; I had taken so much time and effort in preparing for this one course that I had neglected my programming during most of this period, and had become extremely rusty in even constructing linked lists.  As a result, I was unable to complete most of the problem sets for another required course that I had taken during that semester, the above-mentioned “CS 323a:  Introduction to Systems Programming,” and didn’t have enough time to take courses in compilers and interpreters or in operating systems, or to learn linear algebra; consequently, I did not become a programmer for lack of confidence in programming, or proceed on to graduate school in computer science for lack of knowledge of such topics as eigenvectors, eigenvalues, and determinants in linear algebra.  However, I did continue studying computer science (in particular, the field of programming language theory, particularly pertaining to the programming languages Scheme and Haskell) as a hobby in my spare time.

Instead, I plan to start a project to create a virtual world where people can spend most of their lives, including working to earn real-world funds, studying such topics as functional programming and translation, and performing various banking and financial errands which are currently usually performed in the real world, from within the virtual world; I just need a collaborator, preferably familiar with the language Squeak (an implementation of Smalltalk) and the virtual world construction tools Croquet and Cobalt.

My experiences in college and after graduation later inspired me to write the following poem (which is still a work in progress), The Sea of Time, or Once Upon A Program, à la La Divina Commedia by Dante Alighieri, thematically based on my trials and tribulations with the Computer Science major.

(Canto I is based on my experiences in college; Canto II is based on my experiences after graduation from college, but before returning to Tokyo (Francis T. McGrath III was my roommate for a portion of this time) (I had previously resided in Tokyo between August of 1979 and August of 1989, before matriculation at college, graduation, moving to New York, and finally returning to Tokyo in June of 2004); Canto III is based on my experiences after returning to Tokyo. In a sense, the structure of this poem is a microcosm of the structure of La Divina Commedia: Canto I roughly corresponds to the Inferno, in that my life in college was, roughly put, a living hell; Canto II to the Purgatorio, in that my life after college, while significantly less stressful than that in college, seemed like one long odyssey to try, somehow, to obtain enough funds to return to a place within commuting distance of Akihabara; and Canto III to the Paradiso, in that, at long last, after countless trials and tribulations, I finally managed to return to my power source in visiting the mecca of anime and RPG’s: my other two hobbies):

The Sea of Time, or Once Upon A Program

Canto I

To C, or not to C,
Oh, what a mystery

Does life so have to be;
Yet, ever shining sea,

So fresh, so sweet, so deep;
Ever enticingly,

Risk all, for Greatness sake,
In haste, commands so, she.

With trepidation, I
Set warily about.

The sky, so overcast:
Across it race dark clouds,

Yet in the distance shine
Those rays: hopes, zest, and dreams.

Beguilingly, they spark
And beckon to their womb.

Let Daring be my sword,
With Fortitude my shield,

May Youth now be my boat,
With Zest of Life my sail.

The adversary, Time,
Unbeckoned, fans a gale.

He taunts, Thy trip is far,
Your boat shall soon decay,

And when it is no more,
Consume you shall the sea.

So set I on my quest,
In search of new honor,

The storm, so ominous,
Loomed dead ahead, nearing.

As when Poseidon loomed,
His Trident shining bright,

Yet he, Ulysses showed
No fear, but sailed on.

So kept I on my quest,
Regardless of Time’s words,

Full knowing, should I fail,
That doom would lay ahead.

Canto II

‘Twas two months short a year
One day, when sun cast light

Upon a youthful boat
Whom Chance gave luck to meet.

“‘Tis Lafcadio Hearn
Who calls me yonder here,

“That, one day, I might see
A Land of Rising Sun.”

So booms, within the boat,
A voice, so loud and clear

No fear or doubt can rock
Its manifest resolve.

“Whose voice is this I hear,”
Ask I, as we face off.

“‘Tis Francis T. McGrath,
The Third, who asks of thee

“That thou shalt tutor me
On that ancient country.”

“Thou may have, in return,
Such means necessary

“For in that Empire State
A Big Apple to see.”

This contract we both vow,
and onward we journey.

Until one cannot miss
This sight, amid its steeps,

Looming, high above, this
City that Never Sleeps.

Such land where Chaos reigns
Never before have seen!

Inhabitants around
Push others all about,

‘Til not a soul is stout,
Still standing on the ground.

Each warily about,
Gazes, always to doubt,

Whether ’tis safe to trust,
Or else be made to bust.

Canto III

Circle of Hell, each year,
In Big Apple, it was,

As Dante watched from far,
Purgatory to come.

Yet one day at last came:
The Rising Sun arose,

Icarus, stay away!
Let not my wings melt now!

The heavy bird landed,
Its wings made of metal,

Thus dawned a new journey:
Land of the Rising Sun.

The Eastern Capital:
Its Rainbow Bridge at night,

Gleamed bright in the starlight,
The monorail zoomed by.

City of Lights it was,
Scintillating at night.

Each halo gleaming bright,
A ray of hope in sight.

Akihabara now!
At long last, finally!

So many years have passed:
A harsh taskmaster, Time.

But wait shall be no more,
For I am back to see

The land of anime
and role-playing magic.

But wait! Computer shows:
Where have they disappeared?

And all the showrooms gone?
Only an Apple Store?

Something has gone amok!
Audio centers: none!

Roppongi Hills is here,
A labyrinth must-see.

Yet I would rather be
Back in 1980.

— by Benjamin L. Russell
March 13, 2008

From Hofstadter’s “Prolegomena to Any Future Metacat” to Marshall’s “Metacat: A Self-Watching Cognitive Architecture for Analogy-Making and High-Level Perception”: What Is The Mind’s I?

(This content of this post is based on the content of my post [1] entitled “Metacat: A Self-Watching Cognitive Architecture for Analogy-Making and High-Level Perception” on the USENET newsgroup comp.lang.scheme.)

Recently, I stumbled across a rather fascinating project entitled “Metacat: A Self-Watching Cognitive Architecture for Analogy-Making and High-Level Perception” [2], by James B. Marshall.

According to the Overview (see the hyperlinked site above),

Metacat is a computer model of analogy-making and perception that
builds on the foundations of an earlier model called Copycat. Copycat was
originally developed by Douglas Hofstadter and Melanie Mitchell as part of
a research program aimed at computationally modeling the fundamental
mechanisms underlying human thought processes. Central to the
philosophy of this research is the belief that the mind’s ability to perceive
connections between apparently dissimilar things, and to make analogies
based on these connections, lies at the heart of intelligence. According to
this view, to understand the analogical mechanisms of thinking and
perception is to understand the source of the remarkable fluidity of the
human mind, including its hidden wellsprings of creativity.

For those of you who may have read the book Fluid Concepts And Creative Analogies: Computer Models Of The Fundamental Mechanisms Of Thought [3], by Douglas Hofstadter, Copycat was a computer model of analogy-making and perception that sought to examine the underlying process of human creativity by focusing on analogies between patterns of sequences of letters within words.

The name “Metacat” reminded me of a chapter in the book entitled “Chapter 7. Prolegomena to Any Future Metacat,” which itself was probably a pun on the book Prolegomena to Any Future Metaphysics [4], by the Western philosopher Immanuel Kant (German philosopher (22 April 1724 – 12 February 1804)). Although the chapter title is not referenced on the above-mentioned site, since the architect, Marshall, worked together with Hoftstadter, it is highly likely that that chapter title is at least partially responsible for the name of the project.

Copycat lacked the ability of “self-watching”; it was unable to examine how it arrived at its answers, and hence was unable to draw conclusions on a meta-analogical level. Metacat addresses this issue, as follows (see the above-mentioned Overview):

Metacat focuses on the issue of self-watching: the ability of a system
to perceive and respond to patterns that arise not only in its
immediate perceptions of the world, but also in its own processing of
those perceptions. Copycat lacked such an “introspective” capacity,
and consequently lacked insight into how it arrived at its answers. It
was unable to notice similarities between analogies, or to explain the
differences between them or why one might be considered to be
better or worse than another. In contrast, Metacat’s self-watching
mechanisms enable it to create much richer representations of
analogies, allowing it to compare and contrast answers in an insightful
way. Furthermore, it is able to recognize, remember, and recall
patterns that occur in its own “train of thought” as it makes analogies.
For instance, by monitoring its own processing, Metacat can often
recognize when it has fallen into a repetitive cycle of behavior,
enabling it to break out of its “rut” and try something else.

I tried out the Metacat simulation (its runs using Petite Chez Scheme + the Scheme Widget Library (SWL) + Tcl/Tk (version 8.3 or later)) on Windows XP Professional, Service Pack 3 (for which there is a self-extracting installer that installs Petite Chez Scheme, SWL, and Tcl/Tk combined), and it worked! Although it took up a lot of memory and ran rather slowly (the execution speed is adjustable), it graphically represented the analogy-making process in real time.

This kind of self-referencing cognitive project seems ideally suited to Scheme. If anybody knows of any similar self-referencing or reflective [5] projects for which the strengths of Scheme stand out, I would appreciate it if you could post related information below.

Now, back to the main question in the title of this post: What really is The Mind’s I?

[1] Russell, Benjamin L. “Metacat: A Self-Watching Cognitive Architecture for Analogy-Making and High-Level Perception.” Online posting. 11 Nov. 2009. 10 Dec. 2009. <news://comp.lang.scheme>. Also available at <>.

[2] Marshall, James B. “Metacat: A Self-Watching Cognitive Architecture for Analogy-Making and High-Level Perception.” James B. Marshall. 17 Oct. 2009. 10 Dec. 2009. <>.

[3] Hofstadter, Douglas R. Fluid Concepts And Creative Analogies: Computer Models Of The Fundamental Mechanisms Of Thought. New York, NY: Basic Books, Inc., March 21, 1996. <>.

[4] Kant, Immanuel. Prolegomena to Any Future Metaphysics. Cambridge: Cambridge University Press, 1783. <>.

[5] “Reflection (computer science) – Wikipedia, the free encyclopedia.” Wikipedia, the free encyclopedia. 9 Sept. 2003. 10 Dec. 2009. <>.

H. L. Mencken’s Law, and the Inverse Relationship Between Knowledge and Happiness

While walking through the halls of Arthur K. Watson Hall in the Department of Computer Science at my alma mater (a dismal school with Gothic architecture located somewhere in New Haven, the mood of academic tortu*, ahem, of academic pursuit, rather, of which in 1989 to 1994 (including my LOA) was characterized by a local art poster which once depicted a screaming man getting run over a train while muttering “This too shall pass.”), one day in circa 1992 to 1994, I once encountered a sheet of paper pasted to a door of one of the professors of computer science with the following inscription:

Those who can, do.
Those who can’t, teach.
Those who can’t teach, do research.

Later, I came to learn that the first two lines have been attributed to H. L. Mencken (American journalist, essayist, magazine editor, satirist, critic of American life and culture, and student of American English (September 12, 1880 – January 29, 1956)); however, it is not clear who came up with the last line.

In a brief mental journey to that very location in the past, just this evening, I happened to have a dream in which I was back at Old Campus at my college, but this time, as a guide who was showing a visitor around campus while jokingly mimicking the other students. Upon waking up, I somehow came up with my own version of an extension to Mencken’s Law, which I have termed “Russell’s Extension to Mencken’s Law” below:

Those who can, do.
Those who can’t, teach.
Those who can’t teach, write.

— myself

Later, I learned that the extension that I had come up with was very similar to a different extension that someone else had also devised:

Those who can, do.
Those who can’t, teach.
Those who can’t teach, criticize.

— Solomon Short

After some research, I discovered that Solomon Short is actually a fictional alter ego of David Gerrold (American science fiction author (24 January 1944-)), author of The Galactic Whirlpool [1].

(Just to be fair, Nicolas Martin had also previously, without my knowledge, came up with what is sometimes known as Martin’s Extension to H. L. Mencken’s Law:

Those who can, do.
Those who can’t, teach.
Those who can’t teach, teach education.

— Nicolas Martin


These quotes bring to mind another saying that I had also see posted on another door in the same department on another occasion. Although I can’t remember the exact wording (and am unable to find the reference now), the gist was somewhat like the following:

Before going to college, we think that we know everything.
When in college, we learn that there are some things that we don’t know.
When in graduate school, we learn that there are quite a few things that we don’t know.
When in a Ph.D. program, we learn how truly enormous and insurmountable are the things that we really don’t know.

(If anybody knows the source or exact wording of the above-mentioned quote, I would greatly appreciate an explanatory comment with the corresponding information below.)

Incidentally, there can be an inversely proportional relation between knowledge and happiness. In my case, before going to college, I felt much happier than just after graduating, because I did not know how much I did not know. In particular, I felt that I could easily become an astronomer or astrophysicist or any other professional with enough study. Before going to college, I was greatly inspired by the book Cosmos [2] by Carl Sagan (American astronomer, astrochemist, and author (November 9, 1934 – December 20, 1996)), which described a variety of scientific topics related to astronomy and astrophysics. Back then, I used to dream of becoming an astronomer or astrophysicist.

Unfortunately, I had one major problem: Because of financial circumstances, I was unable to attend high school in Tokyo before matriculating at college (I was almost entirely self-taught), and was therefore unable to participate in physics-related lab experiments, which required access to a laboratory. Furthermore, I did not have access to sophisticated books or tutors for physics, and my home environment was very noisy and distracting. Worst, my concentration was repeatedly interrupted every thirty minutes or so by an over-protective parent at home who insisted on bringing pink grapefruit to my desk, and who demanded to know what I was thinking about every time that I tried to contemplate anything deeply. Essentially, I matriculated at college without having had much exposure to physics.

Then I discovered that the introductory courses in physics all assumed more knowledge of physics than I had, so I wound up never taking any courses in physics for lack of time to catch up. Instead, I wound up pursuing computer science, since I had had some exposure to programming. Although I eventually graduated with a Bachelor of Science in computer science, my lack of significant aptitude in mathematics (I initially had to overcome mathematics phobia as well) caused me to lose much sleep in trying to catch up, and I eventually chose not to pursue computer science in graduate school because of fear of over-exhaustion due to even more lack of sleep; I had not mastered linear algebra, in particular, in part because my visiting professor had only spent two weeks on the subject in my discrete mathematics class, and I was very concerned about whether I could catch up with such a serious deficiency, since I was keenly aware of how fundamental and essential this topic would be in any graduate program in computer science.

Paradoxically, however, my great difficulty in overcoming the mathematical prerequisites for computer science did confer one hidden advantage: The process made me much better at explaining mathematical concepts to beginners and to students who are relatively weak at mathematics. After graduation, I once tutored my roommate in mathematics, and he commented then that my explanations were significantly easier to understand than those of his regular mathematics tutor. Later, one of my employers in Manhattan told me that he was much better at teaching a subject than others who knew more about the subject than he did, because he was able to see the subject from the student’s perspective. Paradoxically, my explanations for mathematics have therefore generally been evaluated much more favorably than those for English, which is my forte, because when teaching mathematics, I can understand why the student finds a concept difficult, whereas in English, most concepts seem so trivially elementary that I simply cannot understand how any student could possibly not understand them. Therefore, I have the curious advantage of being much better at explaining those mathematical concepts that I do understand than mathematicians who have never had to struggle in understanding them.

Back to physics, however. Curiously, however, before matriculating at college, I had always found the few books on physics that I had studied to be much more interesting and approachable than equivalent-level books on high school mathematics (in particular, although I enjoyed set theory and, later on, graph theory, I had always had a strong antipathy toward algebra and, in general, toward any areas which did not allow visualization of the concepts). I enjoyed visualizing structures mentally, but had difficulty in doing so in algebra; however, I found visualization much easier in physics. Even in college, when I occasionally encountered physics problems that a tutor nearby was explaining to other students, I was surprised that I did not feel that the problem seemed difficult, since I could readily visualize it. However, I was so overloaded in coping with computer science that I had no spare time in which to explore physics at the time.

In college, I discovered that my visual approach to learning put me at a distinct disadvantage in learning topics that could not readily be approached visually, such as algebra. This discovery made me deeply unhappy. My writing professor told me that I had a flair for writing and actually walked me to the library microfiche collection in recommending that I apply for a graduate program in English, whereas Drew McDermott, my computer science professor for Computer Science 201a: Introduction to Computer Science, had told me that he thought that I was “not cut out for computer science”; nevertheless, I was determined to prove McDermott wrong, and persevered in computer science, eventually completing the major after going through much difficulty in overcoming Computer Science 365a: Design and Analysis of Algorithms. (Curiously, I found the following course, Computer Science 465b: Advanced Algorithms, to be much more manageable than the introductory course, even though the material was more sophisticated, because there was much less material to cover.)

It was not until many years later, a few days ago, while watching a series of educational programs on NHK public television in Japan, that I realized that I actually found the topics in science to be distinctly easier to understand than topics of an equivalent level in algebra; until then, I had thought that the difference would be insignificant. This was when I realized that I might have been better off in a natural science; in particular, physics.

In order to undo my depression from the college experience, I had to restore my mental continuation (to borrow a concept from the Scheme programming language) to just before entering college, and to set aside mentally the entire college experience and accompanying negative emotional weight as a separate continuation, pretending that a different mental process had proceeded with that mental computation. This required visiting some memorable places before college and recovering some emotional memories by walking along some of the same paths and drinking some of the same soft drinks as back then. This brought back the mathematics phobia that I had previously overcome, but at least I was no longer depressed: I had, in a sense, gone back in time mentally and restored my old self, so to speak.

If more knowledge can lead to less happiness, then, by the inverse rule, less knowledge may also lead to more happiness (or at least to a recovery of happiness preceding the greater knowledge).

A corollary is that great souls often are burdened with great unhappiness. Albert Einstein (US (German-born) physicist (14 March 1879–18 April 1955)) once said the following [3]:

If I had only known, I would have been a locksmith.

Wolfgang Amadeus Mozart (composer born in the Archbishopric of Salzburg ((27 January 1756 – 5 December 1791)) died at only thirty-five years of age. Thomas Edison (American inventor, scientist, and businessman (February 11, 1847 – October 18, 1931)) suffered hearing impairment when his chemical laboratory caught fire and the train conductor smacked him on the ears and threw him off the train. Ludwig van Beethoven (German composer and pianist (17 December 1770[1] – 26 March 1827)) reportedly suffered a severe form of tinnitus which caused him great difficulty in hearing his own music; he was also tragically unsuccessful in romance.

I may not be a “great soul” (yet!), but recently, I have come to believe that until I become one, I at least have the benefit of being less unhappy (at least for now).

Recently, I have become more interested in resurrecting my old study of physics, and to see how far I might be able to pursue this subject formally. In particular, I am tentatively entertaining the (admittedly perhaps wild) idea of re-doing my entire undergraduate degree in physics instead of computer science, just to see how far I could go. I have a curious feeling that, because of my visual way of thinking and my greater aptitude for physics than mathematics, I might actually be able to attend graduate school faster by redoing my entire undergraduate education in physics than by trying continue directly on to graduate school in computer science. As a first step, I am considering reviewing some of the Feynman Lectures on Physics [4] at the next available opportunity.

[1] Gerold, David. The Galactic Whirlpool. New York, NY: Random House Publishing Group, 1997. <>.

[2] Sagan, Carl. Cosmos. New York, NY: Random House, Inc., 1980. <>.

[3] Moncur, Michael. “Michael Moncur’s (Cynical) Quotations.” and Michael Moncur. 10 December 2009. 10 December 2009. <>.

[4] Feynman, Richard P., Robert B. Leighton and Matthew Sands. The Feynman Lectures on Physics. London, U.K.: Addison Wesley Longman, 1970. <>.