This thesis explores the processes of discovery and creativity by constructing computer programs which invent interesting constructions and discover significant regularities in their own isolated worlds. It suggests that discovery is best understood as the interaction of two distinct processes: the exploration of possibilities in a given vocabulary and the invention of new vocabularies where such explorations will prove fruitful. The `vocabularies' explored or invented by these processes are not merely the words and definitions one might find in a dictionary or glossary, but are the essential categories, criteria of identity and simplicity, `technical' practices, and descriptive biases involved in both the exploration of possibilities and the reduction of possibilities to practice. Extension or modification of any of these elements may be part of vocabulary invention; in the most radical cases, criteria of identity, simplicity, or reference may be drastically reformulated in the transformation to a new vocabulary.
A program called ``Cyrano'' is used to experiment with the interaction of exploration and invention in discovery; beginning from a base vocabulary of operations on simple recursive structures, Cyrano proceeds to the construction and description of simple arithmetic systems. For Cyrano, a vocabulary is a set of data structures and combining operations together with an opaque interpreter which generates `examples' from data structures; Cyrano's processes of vocabulary invention may either transform the space of data structures it acts upon (by making composites into primitives or abstracting common patterns of combination) or construct new `interpeters' which codify different standards for identity or behavior than those which it was initially given. The invention of new vocabularies is driven by the history of explorations within an existing vocabulary; invented vocabularies are then subject to the same sort of exploration leading (presumably) to the invention of yet other vocabularies.
A central intellectual element of this thesis is that a given result is as much a product of the framework that produced it is a statement or assertion within that framework. The same can be said of this work; I have much to owe for the framework whose threads I attempt to tie together in this document. Parts of the framework are the intellectual environment in which I have had the honor and pleasure to be immersed over the past ten years; other parts are the framework of friends and family who have helped me keep my perspective on my work and my life.
First and foremost, I must thank my thesis committee: Marvin Minsky, my advisor and mentor who showed me how to be playful and critical at the same time; Patrick Winston, who kept my feet on the ground as we stared cloud-wards; Doug Lenat who insisted that my work be both fun and exciting as well as intellectually significant; and Thomas Kuhn, who listened so carefully to my awkward descriptions as to teach me important lessons about both what I was saying and about the importance -- and difficulty -- of trying to figure out what someone means and not merely what they say.
Of equal importance has been the cadre of faculty, graduate students, undergraduates, and otherw who have created the intellectual ambience in which these ideas and this author matured. In no particular order, Phil Agre, David Chapman, Gary Drescher, Ken Forbus, Dan Weld, Dan Huttenlocher, John Batali, Jim Davis, Diane Dustman, Margaret Minsky, Pattie Maes, Walter van der Velde, Luc Steels, Rick Lathrop, Jonathan Amsterdam, John Mallery, David Wallace, Gerry Roylance, Tom Knight, Ramesh Patil, Gerry Sussman, Ian Horswill, Marty Hiller, and many I must have forgotten have all shaped me and this work with discussions, debates, and humorous exchanges.
Many of the individuals above have, along with me, been participants in the adventure known as the MIT Artificial Intelligence Laboratory. In helping to maintain a maximally hassle-free, relatively egalitarian, and -- most importantly -- comfortable place, I'd like to thank Priscilla Cobb, Marilyn Melithoniotes, Cody Curtis, Rita Boyland, Cathleen Krebs, and (again) many others. My work in particular has been funded by the Office of Naval Research through either the auspices of Marvin Minsky or Patrick Winston; their support is gratefully acknowledged.
My friends and family, too many to be thanked individually, have been a support during all the process of graduate school. Thank you and I love you all.