
Home  Invited Speakers  Lectures  Program  Local Infomation  Contact Us  



Mathematical logic was developed in an effort to provide formal foundations for mathematics. In this quest, which ultimately failed, logic begat computer science, yielding both computers and theoretical computer science. But then logic turned out to be a disappointment as foundations for computer science, as almost all decision problems in logic are either unsolvable or intractable. Starting from the mid 1970s, however, there has been a quiet revolution in logic in computer science, and problems that are theoretically undecidable or intractable were shown to be quite feasible in practice. This talk describes the rise, fall, and rise of logic in computer science, describing several modern applications of logic to computing, include databases, hardware design, and software engineering. 




Our dependence on software is now pervasive and reaches many aspects of our lives: most work, including work in all large organizations, most industrial work and even increasingly agriculture, is now softwaremediated. Many of our interactions with the physical world and with our social world are likewise software mediated. The systems involved are very large and increasingly complex, and the economic and human cost of failures and vulnerabilities is enormous. It is hard to disagree with any of this; or with the need for higher software quality and reliability. What is not so clear is what to do about it. 




Underlying all software development are two key concerns: correctness and efficiency. Logic plays a fundamental role in reasoning about correctness. Combinatorics plays a fundamental role in reasoning about efficiency. In modern times it has come to be realized that probability theory is a powerful tool for combinatorial reasoning. Handinhand with this is the discovery of the power of probabilistic algorithms. What is less widely appreciated is that probability is equally important for the development of correct software. 




We develop coarsegrained models of the cell; explain the inherent resource allocation problem which the cell has to solve; and derive from a simple model constraints on the cell's steady state chemical composition which have been empirically identified as the "growth laws". 
