Knowledge Based Algorithms, Fall 2003.

Computers are useless; they can only give answers. (Pablo Picasso.)

This Fall, I am again going to teach Knowledge Based Algorithms. The previous experiences with this course, (which is still experimental,) are described below, and for more information you can download the paper of Ryan Pepper from the web page of Craig Larson http://www.math.uh.edu/~clarson/ This semester, the course will be closely related to new conjectures of the benzenoid and fullerene versions of the computer program Graffiti (see http://www.math.uh.edu/~siemion/pony.html). Apart from this, we will also discuss Graffiti and other AI discovery systems in the context of the Turing test.

As before, no previous knowledge of mathematical chemistry or graph theory is assumed, and the only prerequisite is graduate standing in the College of Natural Sciences and Mathematics or consent of the instructor. There is also a possibility of taking this course on a purely distance-learning basis, since a good part of the course will be conducted via a discussion list in any case. If you are interested in this option, please discuss it with me. As before, this class may count toward the Mathematics requirements of a Computer Science M.S. or Ph.D. degree, with approval of the department.

Here are previous experiences with this course. In the spring of 2001, I taught a Texas-style course based exclusively on conjectures of Red Burton - an educational version of Graffiti. We began with a 1-vertex example. Not surprisingly, initially most of the conjectures were false. To acquire theorem-proving skills, participants were asked to provide a smallest counter-example to each of the refuted conjectures. We began with selecting a small set of simple invariants, tried to stick to it, and to not proceed any further with conjectures until a smallest counter-example was found. At about the same time, Ermelinda DeLaVina at UHD ran a similar experiment with her undergraduate student Barbara Chervenka. Barbara presented a poster about it at CombinaTexas 2001, Texas A&M.

In fall of 2001, I began to teach "Knowledge Based Algorithms," but most of the ideas crystallized in the fall of 2000, when Jimmy Pritts - an undergraduate aficionado of Texas style - took a tutorial with Graffiti. Thanks, Gordon. In the nick of time (after more than a decade of agonizing about it) it dawned on me that one could plant two trees with one seed: that the only difference between educational and possible fully automated research versions of Graffiti could be the concepts about which the machine makes her conjectures. It was always my favorite method of running the program anyway - starting each of the (Dalmatian) versions from scratch. The only difficulty is that this approach requires discipline that can be expected more of machines than humans.