Vaughan Pratt


DIMACS Center - Rutgers University
CoRE Building, 1st Floor Lecture Hall
Piscataway, New Jersey
Tuesday, July 23, 1996
11:00 AM

Topic of Discussion

CHU SPACES: SMART BEHAVIOR FROM SIMPLE OBJECTS

Abstract:

Chu spaces, defined by M. Barr at McGill and studied by his student P. Chu in the 1970's, are rectangular matrices over a given set that transform by duplicating and deleting columns, identifying equal rows, and adjoining new rows. With these transformations Chu spaces form a richly endowed category, being self-dual, bicomplete, and symmetric monoidal closed, and hence a model of Girard's linear logic.

Our motivating interest in Chu spaces has been as a universal model of computation. More recently and to our considerable surprise, we have found that every algebraic and/or topological object of mathematics is representable as a Chu space, in such a way that the above transformations are in one-to-one correspondence with those functions that are homomorphisms and/or continuous when definable traditionally. Restating this in categorical language, the many diverse categories of mathematics all embed fully and concretely in different regions of the one category of Chu spaces, whose objects may then be understood as spanning the gamut from sets as the most discrete objects of mathematics to complete atomic Boolean algebras, aka antisets, as the most coherent.

There being no explicit notion of either signature or theory here, this implies that every Chu space must come with both signature and theory built in implicitly, along with the ability to communicate appropriately with objects having both similar and dissimilar signatures. The talk will focus on explaining how such an unsophisticated mechanism can exhibit such sophisticated behavior.

About the Speaker:

Vaughan Pratt is Professor of Computer Science at Stanford University. From 1972 to 1982 he was on the Electrical Engineering and Computer Science faculty at MIT. He helped found Sun Microsystems in 1982 and is the designer of Sun's logo and the Pixrect graphics system. He worked in natural language, analysis of algorithms, and logics of programs in the 1970's, and concurrency modeling, computer graphics, and digital typography in the 1980's. His current interest is Chu spaces and their many applications. His bachelor's and master's degrees are from Sydney University, and his Ph.D. (1972) is from Stanford University, advisor Donald Knuth.

This is the final speaker in the Distinguished Lecturer Series of the DIMACS Special Year on Logic and Algorithms.

For additional information about the DIMACS special year, please see the following web site:

http://dimacs.rutgers.edu/archive/SpecialYears/1995_1996/


Index

dimacs-www@dimacs.rutgers.edu
Document last modified on June 11, 1996