Speaker:

Noson S. Yanofsky

Monday, July 22, 2013 - from 14:00
to 14:40

Abstract:

Category theory and its structures play major roles in modern mathematics, theoretical computer science, and theoretical physics. We will give a type of objective measure to the information content of these structures by formulating the notion of Kolmogorov complexity of categorical structures. Classically, Kolmogorov complexity tells the algorithmic information content of a string by looking at the length of the shortest program that describes the string. We formulate a programming language that can describe categorical structures and define the algorithmic information content, $K(\bf X)$, as the length of the shortest program that describes the structure ${\bf X}$.
We prove that if $\A$ and $\B$ are equivalent categories than $K(\A)$ is the same as $K(\B)$. This makes our Kolmogorov complexity a invariant of categorical structure. We apply Kolmogorov complexity to algebraic theories and monads and show that it is an invariant of algebraic structures.
Along the way we show that every computable functions can be constructed as a functor. We show that we can use categories to mimic Turing machines and prove that our notion of Kolmogorov complexity is the same (up to a constant multiple) of the classical notion. Since one can perform infinitary operations in category theory, our programing language can solve the Halting problem for Turing machines. But it cannot solve the halting problem for categorical constructions. We make some progress to tell exactly what is the power of categorical constructs.
We make several steps towards a generalization of the Kolmogorov complexity version of G\"{o}del's incompleteness theorem.
We also discuss this work in context of Occam’s razor. This is a criterion in which to judge different physical theories. In short, physicists formulate functors from some category of physical phenomena to a category of mathematical structure. Occam's razor demands that the second category have low informational content. We feel that with a better understanding of this we would be able to answer the question of why it seems that Occam's razor works so well.