Undergraduate Colloquium

Claims of computer programs making discoveries in mathematics and science go back to several famous AI works including Herb Simon's - a Nobel and a Turing prize winner. Yet authentic discoveries, did not happen until eighties when conjectures of Graffiti - a program written at the University of Houston, began to inspire papers by many mathematicians including Paul Erdös. In response, Simon made a claim that no program can make at this stage discoveries in physical sciences. Graffiti's response, was the independence-stability hypothesis: classical fullerenes tend to minimize maximum sets of their mutually not bonded carbon atoms.

Classroom use of Graffiti proved to be harder, and it was not fully accomplished, until Stephanie Mathew, an undergraduate at the time, attempted to simplify an argument that soon led to 3 new proofs of Euler's Characteristic formula, relating it, surprisingly to even better known results of Euler. This talk is based primarily on my joint paper with Stephanie and "Program Accelerators", inspired by Simon's impossibility claim, both written within the past three years, conjectures of Graffiti obtained this semester that already inspired work of some undergraduate and graduate students, and, as usually, some very well-known researchers. The second paper generalizes the Universal Turing Machines claim to an "axiom" according to which one can write, a program Mach that for any input program P, can rearrange itself into a program Mach(P), performing the same task as P, but possibly much faster, in principle, having a potential for conjecturing programs showing that P = NP.