Physics and Computation

Abstract

This thesis is an exploration of some places where ideas in computer science and physics share a common mathematical structure. The first part of the thesis deals with partition functions in physics and algorithmic information theory. In physics, partition functions are used to encode information about statistical systems in thermal equilibrium; in algorithmic information theory, they are used to encode information about the probability that a Turing machine will halt given a random program. We derive analogues of Maxwell’s relations in the algorithmic setting and consider thermodynamic cycles such as the Carnot cycle or Stoddard cycle. We also show that given a program and a probability P, we can effectively compute a time after which the probability that the program will eventually halt is less than P. This idea of a time cutoff is reminiscent of a high-energy cutoff in renormalization. The second part of the thesis reviews symmetric monoidal closed categories and bicategories. We begin with an expository chapter on symmetric monoidal closed categories and demonstrate how they form a broad generalization of the Curry-Howard isomorphism, including string diagrams in physics, cobordisms in topology, multiplicative intuitionistic linear logic, and the simply-typed lambda calculus in computer science. We then go up one dimension and present the complete definition of a special kind of symmetric monoidal closed bicategory called a compact closed bicategory. We emphasize the combinatorial aspects and prove that given a 2-category T with finite products and weak pullbacks, the bicategory Span2(T) of objects of T, spans, and isomorphism classes of maps of spans is compact closed. As a corollary, certain bicategories of “resistor networks” are compact closed.