Kolmogorov Complexity of Categories

arXiv:1306.2675v1 [math.CT] 11 Jun 2013

Noson S. Yanofsky
Department of Computer and Information Science, Brooklyn College, CUNY,
Brooklyn, N.Y. 11210.
and the Computer Science Department of the Graduate Center, CUNY,
New York, N.Y. 10016.
noson@sci.brooklyn.cuny.edu∗

Abstract. Kolmogorov complexity theory is used to tell what the algorithmic informational content of a string is. It is defined as the length of
the shortest program that describes the string. We present a programming language that can be used to describe categories, functors, and
natural transformations. With this in hand, we define the informational
content of these categorical structures as the shortest program that describes such structures. Some basic consequences of our definition are
presented including the fact that equivalent categories have equal Kolmogorov complexity. We also prove different theorems about what can
and cannot be described by our programming language.
Keywords: Kolmogorov Complexity, Algorithmic Information, Categories, Functors, Natural Transformations.
Dedicated to Samson Abramsky in honor of his 60th Birthday

1

Introduction

Kolmogorov complexity is a part of theoretical computer science that was pioneered in the early 1960’s by Andrey Kolmogorov, Ray Solomonoff, and Gregory
Chaitin. For reasons ranging from probability theory, to machine learning, and
A while back, I showed some of these ideas to Samson Abramsky and he was, as
always, full of encouragement and great ideas. I am very grateful to him for all his help
over the years. I would like to acknowledge the help and advice of Michael Barr, Marta
Bunge, James Cox, Joey Hirsh, Florian Lengyel, Dustin Mulcahey, Philipp Rothmaler,
and Louis Thral. I want to thank Shayna Leah Hershfeld for many enlightening conversations about polymorphism and type theory. Support for this project was provided
by a PSC-CUNY Award, jointly funded by The Professional Staff Congress and The
City University of New York.
∗

computational complexity theory, these three researchers gave a universal definition of what it means for a string of symbols to be simple or complex.
Consider the following three strings:
1. 00000000000000000000000000000000000000000000000
2. 11011101111101111111011111111111011111111111110
3. 01010010110110101011011101111001100000111111010
All three consists of 0s and 1s and are of length 45. It should be noticed that if
you flipped a coin 45 times the chances of getting any of these three sequences
are equal. That is, the chances for each of the strings occurring is 1/245 . In effect,
this shows a failure of classical probability theory in measuring the contents of
a string. Whereas you would not be shocked to see a sequence of coins produce
string 3, the other two strings would be surprising. The difference between these
strings can be seen by looking at short programs that can describe them:
1. Print 45 0’s.
2. Print the first 6 primes.
3. Print ‘01010010110110101011011101111001100000111111010’.
The shorter the program, the less informational content of the string. In contrast,
if only a long program can describe the string, then the string has more content. If
no short program can describe a string, then it is “incompressible” or “random.”
In classical Kolmogorov complexity, rather than talking about programs, one
talks about Turing machines. For a string s, the the Kolmogorov complexity,
K(s), is defined as the size of the smallest Turing machine that starts with
an empty tape and outputs s. Formally, let U be a universal Turing machine,
then K(s) = min{|p| : U (p, λ) = s}. We will also need relative Kolmogorov
complexity: let s and t be two strings, then K(s|t) is the size of the smallest
Turing machine that starts with t on the tape and outputs s. Formally, K(s|t) =
min{|p| : U (p, t) = s}. If K(s) > |s| then s is “incompressible” or “random”.
This notion of Kolmogrov complexity is used in many different areas of theoretical computer science. It gives an objective measure of how complicated strings
are. It is our goal to extend these ideas to many other areas of mathematics,
computer science and physics by formulating a notion of Kolmogorov complexity
for category theory which is used in all these diverse areas. In order to measure
how complicated categories, functors, and natural transformations are, we need
a programing language that will describe these categorical structures. In honor
of Sammy Eilenberg, one of the founders of category theory who also had a deep
interest in computer science, we call this programming language “Sammy.” This

language will have variables that can hold categories, functors and natural transformations. The operations of the language will perform common constructs that
people use to formulate different structures. Each line of the program could have
a label that will be used with ”If-Then” statements to control the execution of
the program.
Notice that numbers, strings, trees, graphs, arrays, and other typical data
types are not mentioned in our programming language. This was done on purpose. The other data types can be derived from the categorical structures. Categories and algorithms are more “primitive” than numbers, strings, etc.
This is not the first time a programing language has been formulated to describe categorical structure. An important example is in Computational Category
Theory by Rydeheard and Burstall [3]. Tatsuya Hagino’s thesis [2] is another example. These languages are, however, different from Sammy. Their programming
languages are made to be implemented and to get computers to actually calculate
with categories. In contrast, there is no intention of implementing Sammy. Our
goal is simply to compare different structures by comparing the length of their
descriptions. In fact, we will not even write many formal Sammy programs. This
is similar to the fact that no one actually ever formally writes the instructions
for a Turing machine.
With Sammy, we will talk about the Kolmogorov complexity of categorical
structures. We discuss when one structure is more complicated than another. We
will also talk about compressibility and randomness. Along these lines, here is a
simple example of the type of ideas we will meet. Consider N, the totally ordered
/1
/2
/ · · · , and 2, the category
category of natural numbers 0
∼ /
1 . A functor
with two objects and a single isomorphism between them 0
F : N −→ 2 corresponds to an infinite sequence of zeros and ones. The category
N
of all such functors 2 is essentially to the real numbers and has uncountably
many elements. How many of these functors can be mathematically described?
There are only countably many computer programs that describe such functors.
This means that the vast majority of functors N −→ 2 cannot be described by
any program and are essentially random.
Not every categorical structure can be described with our programing language. Categorical structures that can be described by Sammy will be called
“constructible.” For example, I do not know how to start from nothing and
make the category of smooth manifolds. However it is probably possible to start
from the category of topological spaces and get the category of smooth mani-

folds. This brings us to the notion of relative Kolmogorov complexity. We will
be interested in how long does a program have to be in order to construct a
categorical structure given some categorical structures.
The fact that certain structures are not constructable with Sammy brings in
the whole area of computability theory. There are limitations to what Sammy
can perform. Usual self-referential limitations are based on variations of the liar
paradox (“This statement is false”) such as Gödel (“This statement is unprovable”) or Turing (“This program will output the wrong answer when asked if it
will halt or go into an infinite loop”) (see [5] for a comprehensive survey of such
limitations.) In contrast, the limitations of Kolmogorov complexity are based on
the Berry Paradox: consider the number described by “The least number that
needs more than fifteen words to describe it.” This sentence has twelve words.
That is, there is a description of a number that is shorter than it is supposed to
be. One such limitation within classical Kolmogorov complexity[4] is:
Theorem 1 K : Strings −→ N is not a computable function.
We will show that there are similar limitations for our Kolmogorov complexity
theory.
Section 2 introduces Sammy. That section also describes several “library
functions” or “macros” in Sammy which will be helpful in the rest of the paper.
Section 3 is the heart of the paper where we define and prove many of the central
theorems about our complexity measure. Section 4 is a discussion of computability and non-computability with the Sammy language. The paper concludes with
some possible ways this work will progress in the future.

2

A Programing Language for Categories

In order to describe categorical structures, we need a programing language. This
language will be called “Sammy”. The language will consist of typical operations that are used to describe/create different categories, functors and natural
transformations. Programs will be lists of statements that set variables to different values. The variables could be categories, functors, or natural transformations. Since categories are special types of functors, and functors are special
types of natural transformations (that is, natural transformations are the deepest type), we might state everything in terms of natural transformations. But
that would make the programs needlessly complex. Rather, for the sake of simplicity, we will be ambiguous about the types of our statements (that is, our

operations/functions will be polymorphic.) As we have absolutely no intention
of implementing Sammy, we can be vague about certain issues.
We begin with constants. There is 0, the empty category, 1, the category
with one object and one morphism, and 2, the category 0 −→ 1 with two objects and one nontrivial morphism. We will also need the constant category Cat
which corresponds to the category of all small categories. There are also several
constant functors: s : 1 −→ 2 and t : 1 −→ 2 that picks out the source and target of the nontrivial morphism in 2. There are the unique morphisms ! : 0 −→ 1,
! : 0 −→ 2, ! : 0 −→ Cat, ! : Cat −→ 1, and ! : 2 −→ 1. There are also identity
functors and natural transformations.
There are several operations that take a single input. For a functor F : A −→
B if we set C = Source(F : A −→ B) then C = A. That is, Source takes a functor
and outputs the category that is the source of the functor. There is a similar
operation C = Target(F : A −→ B). For a given category A, the operation
F = Ident(A) makes F = IdA . For a category A, if we let C = Op(A) then
C = Aop . The Op operation also acts on functors.
We will at times have to talk about an actual object and morphism in the
category. So for example, a functor F : 1 −→ C “picks” an object c in C and a
functor F : 2 −→ C “picks” a morphism f : c −→ c′ . Going the other way, an
object c in C “determines” a functor Fc : 1 −→ C and similarly for a morphism
in C. We write this in Sammy as c = Pick(F : 1 −→ C) and Fc = Determine(c).
For natural transformations of the appropriate source and target there is a
horizontal composition and vertical composition written as α = Hcomp(β, γ) and
α = Vcomp(β, γ). Regular composition of functors is simply a special case of
horizontal composition. For categories A and B, we will have C = Pow(A, B) be
the category of all functors and natural transformations from A to B.
Probably the most important operations are the Kan extensions. For functors
G : A −→ B and F : A −→ C, a right Kan extension of F along G is a
pair (R, α) = KanEx(G, F ) where R : B −→ C and α : R ◦ G −→ F . A Kan
extension induces another functor that is unique. For every H : B −→ C and
β : H ◦G −→ F there is a unique γ = KanInd(F, G; H, β) where γ : H −→ R and
satisfies α · γG = β. Using Kan extensions one can derive, products, coproducts,
pushouts, pullbacks, equalizers, coequalizers, (and constructible) limits, colimits,
ends, coends, etc. It is a well-known fact that if G : A −→ B is a right adjoint
(left adjoint, equivalence, isomorphism), then its left adjoint (right adjoint, quasi-

inverse, inverse) G∗ : B −→ A can be found as a simple Kan extension of the
identity IdA along G, that it, G∗ = KanEx(G, IdA ).
For “bootstrapping” purposes we will need an operation that takes two categories and gives their coproduct and their induced maps. This will help us create
categories like 1⊔1 which will be needed for our Kan extensions to describe products and coproducts; and 2 ⊔ 2 which will be needed to describe equalizers and
coequalizers.
There is a dual notion of a Kan Lifting. For functors F : A −→ B and
G : C −→ B a Kan lifting of F along G is a pair (R, α) = KanLif(G, F ) where
R : A −→ C that satisfies a universal property which can easily be written down.
Since Kan extensions and Kan liftings are only defined up to a unique isomorphism, we might ask what is the output of the function KanEx(G, F )? We
do not care. The computer decides which of the many possible outputs it will
output. It is irrelevant from the categorical perspective. This is similar to a real
programing language when we do not know how something is stored or how a
function is calculated. The user is ambivalent as to how the computer does certain actions. We are also well-aware that the Kan extensions and Kan liftings
might not exist. In that case, the program will not go on.
There is one more operation that needs to be discussed. Let C be a category.
2

C and C1 are the categories of arrows and objects of C. The maps s : 1 −→ 2
and t : 1 −→ 2 induce (using the Pow operation on functors) maps Cs : C2 −→
C1 and Ct : C2 −→ C1 . The pullback of these two maps, C2 ×C1 C2 is the
composable arrows in the category. The important part of the information about
the category is the composability map ◦ : (C2 ×C1 C2 ) −→ C2 . This map will
help us get into the nitty-gritty of how a category is defined. So we have the
following operation: for a category C, the operation F = Composable(C) gives
us the ◦ map.
We would like some control of how the Sammy program will execute. We do
this with a conditional branch statement: If α1 == α2 Goto L where α1 and
α2 are natural transformations and L is a label of some program line. With such
a conditional branch, we can get all the usual logical operations: AND, NOT,
etc. We can also get the unconditional branch Goto L.
There are a number of remarks that need to be made about Sammy:
This might not be the best language for our purposes. Certain operations can
be derived from other operations and hence a smaller more compact language is
possible. For example, the Target operation can be derived from the Source and

Op operations. Bear in mind that our goal is to count the number of operations
up to a coefficient. So we need not be exact. If one operation can be replaced by
a constant number of other operations, nothing is lost.
This language can not describe all constructions. (We shall see later.) What
can be done with this language will be called “constructible.” It is interesting to
look at what type of categories can be described by this programming language
with no other input.
There is a need for a Church-Turing type thesis. The classic Church-Turing
thesis says that whatever can be computed, can be computed by a Turing machine. We need such a thesis that says that whatever can be constructed by
categorical means, can be constructed using the Sammy programing language.
Alas, this is a thesis and not a theorem because we cannot characterize what
can be constructed by categorical means. We will see that there are certain constructions that cannot be performed by Sammy. However, we believe that no
programming language can make those constructions.
With classical Kolmogorov complexity, there is much discussion about “selfdelimiting” programs. This will not be an issue here. We can easily tell when a
Sammy program begins and when it ends.
With Sammy in hand, we introduce some library functions or macros that
will be used in the future:

s

The coequalizer 1
s

/
o
/ 2 ⊔ 2 gives the category ∗

∗

/ ∗ which

can be put in a Kan extension and give us pushouts and pullbacks. We can make
many similar constructions.
For functors L : A −→ C and R : B −→ C we can construct the comma
categories as the following pullbacks:
L ↓ R❍
❍❍
✈✈
❍❍
✈
❍❍
✈✈
✈
❍❍
✈
✈
z✈
$
C ↓ R❉
L ↓ C■
■■
✉
❉❉
③
■■
✉✉
❉❉
③③
✉
③
■
✉
❉❉
■■
③③
✉✉
❉❉
■
✉
③
z✉
$
|③
"
B
C2 ■
A❊
■
❊❊
■■
✉✉
②②
✉
②
❊❊
■■
✉✉
②②
❊
■
✉✉ Cs
②② R
L ❊❊❊
Ct ■■■
②
②
|
" z✉✉✉
$
C
C
Special instances of comma categories are slice categories and coslice categories.

s

The coequalizer 1
t

/
/2

ρ

/ ω gives the (infinite) natural numbers as

a monoid. N = ω 2 gives the totally ordered category of natural numbers. The
successor function is defined as follows:
∼

r:ω

/ ω×1

Id×s

/ ω×2

Id×ρ

/ω×ω

◦

/ ω.

That is, take any n ∈ ω and associate it with the nontrivial morphism in 2. This
becomes the +1 member of ω. Then compose n with +1. Now take this map r
and look at s = r2 : N = ω 2 −→ ω 2 = N. This is the successor map.
We construct the category with two objects and a unique isomorphism between them. First make a category with two distinct copies of 2. By keeping
track of the inclusion maps, we have an induced F and G
❣❣3 1 ⊔✤ 1 k❲❲❲❲❲❲
❣❣❣❣
❲❲❲❲❲inc
✤
❲❲❲❲❲
❣
F
❣
❣
❲❲❲❲t ❲
✤
s❣❣❣❣ /
❣
o

❣
❲❲❲❲
❣
inc
inc
❣❣
❣❲
/
o
2
1❲
2
⊔
2
2
❲❲❲❲❲
❣❣❣ 1
✤
O
o
/
❲
❣❣s❣❣❣
❣
❣
t ❲❲❲❲❲❲
✤
❣
❣❣❣
❲❲❲❲❲
❣❣❣❣❣inc
❲❲❲❲❲ G ✤
inc
❣
❣
❣
❣
❲+
s❣❣
1⊔1
❣
inc
❣❣❣❣❣

Now use these induced maps in a coequalizer to form the desired category. The
figure on the right is helpful.
1⊔1
F

G

 
2⊔2

2

3

∗

∗ ◆◆◆
♣ ∗ ❃❃
◆◆◆
♣♣♣
❃❃
♣
◆◆◆
♣
❃❃
◆◆◆♣♣♣♣♣
❃❃
◆
♣

◆
♣
' o
/ ∗ w♣
∗
∗

∗o

∼

/∗

Kolmogorov Complexity of Categories

For a category C (or a functor, or a natural transformation) we define KSammy (C)
to be the number of operations in the smallest Sammy program that describes
C. For relative Kolmogorov complexity, letting
Γ = {C1 , C2 , . . . , Cl , F1 , F2 , . . . , Fm , µ1 , µ2 , . . . , µn },

or Γ as a sub2-category of Cat then KSammy (C|Γ ) is the number of operations
in the smallest Sammy program that describes C given Γ as input. We shorten
KSammy to K when no confusion will arise.
If there is a finite number of operations so that one can go from one categorical
structure to another and vice versa, we say that the Kolmogorov complexity of
these categorical structures are approximately the same. In detail, if there exists
a c such that for all appropriate categorical structures, X, one can change X to X′
and vice versa in c Sammy operations, that is |K(X) − K(X′ )| ≤ c, then we write
K(X) ≈ K(X′ ). As an example, notice that only one Sammy operation is needed
to go from category A to functor IdA and vice versa. Hence K(A) ≈ K(IdA ).
There is a need for something called an invariance theorem. This basically
says that the Kolmogorov complexity does not depend on the programing language that is used to describe the objects. Imagine that you do not like the
Sammy programing language to describe categorical structures and you decide
to invent your own. Perhaps you call it “Saunders” (after the other founder of
category theory, Saunders Mac Lane.) Then since presumably both languages
can program any constructable categorical structure, they can each program the
other’s operations. That means there exist compilers that can translate Sammy
programs into Saunders programs and there are compilers that can translate
Saunders programs into Sammy programs. From this, we can prove the following theorem: There exists a constant c such that for all categorical structures X
we have |KSammy (X) − KSaunders (X)| ≤ c.
Rather than list all the results we have for K, let us examine some paradigmatic theorems:
Theorem 2 There exists a constant cpair such that for all C and D we have
K(C × D) ≤ K(C) + K(D|C) + cpair .
This essentially says that there is a simple way of taking two categories and
forming their product. There is no new information added. But lets look more
carefully at what the theorem say. It says that to form C × D one can form C
and then form D (but you might use some information that you already have
since you already formed C) and then do a few lines of Sammy to get their
product. The reason for the inequality is because there might be an easier way.
For example 0 × D can be formed in a constant amount of operations: it is 0.
There is also a similar theorem with C and D swapped on the right side of the
inequality.

Theorem 3 There exists a constant cdouble such that for all C we have K(C × C) ≤
K(C) + cdouble .
That is, there is a simple way to double a category and no new information is
there.
Theorem 4 There exists a constant ctarget such that for all F : A −→ B we
have K(B) ≤ K(F : A −→ B) + ctarget .
This means that one way to describe B is to first find a program for a functor
F : A −→ B and then use the Target operation to get B. The inequality comes
from the fact that there might be shorter programs to describe B. There are
similar such theorems for the source of a functor, for natural transformations,
for identity functors, etc.
We state the following theorem about composition in terms of natural transformations for generality.
Theorem 5 There exists a constant ccompos such that for any three natural
transformations α : F −→ G, β : F −→ H, and γ : G −→ H such that β = γ ◦ α
we have
K(β) ≤ K(α) + K(γ|α) + ccompos .
When γ is the unique natural transformation that satisfies this triangle (e.g.
when α is mono) then the inequality in the above theorem becomes an equality.
The theorem for Kan extensions is similar.
Theorem 6 There exists a constant cKan such that for all G : A −→ B and
F : A −→ C if (LanG (F ), α) is the left Kan extension, than
K((LanG (F ), α)) ≤ K(F ) + K(G|F ) + cKan
or for relative Kolmogorov complexity
K((LanG (F ), α)|Γ ) ≤ K(F |Γ ) + K(G|Γ, F ) + cKan .
As a special case, if G : A −→ B is a right adjoint (left adjoint, equivalence,
or isomorphism), then the Kan extension along G of the IdA is the left adjoint
(right adjoint, quasi-inverse, inverse) G∗ : B −→ A. Since it is easy to go from
one to the other, we have that K(G) ≈ K(G∗ ). Notice that for an arbitrary
adjunction, this does not mean that K(A) ≈ K(B) (we shall see that it is

true for an equivalence). Nor does there seem to be any hard-and-fast rule that
says something like a left adjoint goes from something with a low Kolmogorov
complexity to a high Kolmogorov complexity. It is easy to find counterexamples
to such ideas.
If G : A −→ B and F : A −→ C are functors, R : B −→ C is a right Kan
extension, H : B −→ C, and β : H ◦ G −→ F then for the unique induced
γ : H −→ R, we have that K(γ) ≈ K(β). The reason for this is that you can
go from one to the other using composition and the KanInd operation. A simple
example of this is product:
H❍
❍❍
✈✈
❍❍β1
✈
✈
❍❍
✈
!γ
❍❍
✈✈
✈

$
z✈
F0 o α0 F0 × F1 α1 / F1
β0

It is easy to see that the information in γ is exactly the information in the βs.
It is easy to derive one from the other.
Our work would be in vain if the measure we described was not an invariant
of categorical structure. We have the following important theorem.
Theorem 7 If categories A and B are equivalent, then KSammy (A) ≈ KSammy (B).
Proof. The intuition behind the theorem is that Sammy cannot distinguish
categorical structures that are isomorphic. Say the equivalence is given by the
functor G : A −→ B. From G its easily constructed quasi-inverse is G∗ : B −→ A.
We then have that K(G) ≈ K(G∗ ). We also get that K(G ◦ G∗ ) ≈ K(G∗ ◦ G).
If α : IdA −→ GG∗ is the isomorphic unit of the equivalence given by the Kan
extension, then α−1 : GG∗ −→ IdA is easily constructed (we are assuming that
Kan extensions work on natural transformations). Since α−1 ◦ α = idId we get
that K(α−1 ) ≈ K(IdA ) . We then have
K(A) ≈ K(IdA ) ≈ K(GG∗ ) ≈ K(G∗ G) ≈ K(IdB ) ≈ K(B).
QED.
There are some important consequences of this theorem. One can easily cons
/
∼
=/
C
Cskeletal . This
struct the skeletal category as the coequalizer C2
/
t

gives us K(C) ≈ K(Cskeletal ).

In a future paper [6] we will discuss algebraic theories, monads, Morita equivalence and other algebraic notions from the Kolmogorov complexity perspective.

4

Computability and Non-Computability with Sammy

There might be a need to deal with finite numbers. We shall let the number n
correspond a triple (n, Pb , Pe ) where n is the totally ordered category with n ele/1
/ ···
/ n−2
/ n − 1 ), Pb : 1 −→ n
ments (keep in mind: 0
is a functor that points to the beginning of the category (the initial object), and
Pe : 1 −→ n is a functor that points to the end of the category (the terminal
object.) Basic operations with such numbers are easy to describe. For example,
we can connect (n, Pb , Pe ) and (m, Pb′ , Pe′ ) to get (n + m − 1, Pb , Pe′ ) with the
Pb′

coequalizer: 1
Pe

/

/ n⊔m

/ (n + m − 1) . (In truth, natural numbers can

simply be given as functors 1 −→ N. We can manipulate numbers by manipulating such functors. While this is simple and economical, there is a certain appeal
to doing it the way we did. Many prefer to think of their numbers as “things”
and not just pointers to amounts.)
All the finite totally ordered sets should be considered subcategories of N
and, as such, inherit a partial successor function. Before applying this successor
function we must check to make sure that the pointer is not at the Pe position.
A totally ordered category with n elements can be constructed in O(log2 n)
number of Sammy statements. Basically, the idea is that one can look at the
binary representation of n and write a program based on that. For example 727
in binary is 1011010111. We can express this number as
(((((((((1 × 2 + 0) × 2 + 1) × 2 + 1) × 2 + 0) × 2 + 1) × 2 + 0) × 2 + 1) × 2 + 1) × 2 + 1).
Similarly when making our totally ordered category, we can either (a) double
the length of the category by connecting one copy of itself to itself, or (b) double
itself and add one, depending on the bit at that position. This proves that
K(n) ≤ O(log2 n) which is similar to the classical case.
Notice that the above algorithm did not have any input. In contrast, we can
look at a program that loops through input, reads the bit and performs either
(a) or (b). This input will be given as a functor from log2 n to 2. The program
moves a pointer forward on log2n. There will be a conditional branch to see

if the pointer is equal to Pe . While this might be a long program, it does not
depend on the size of the input. We have thus proved that
K(n |

(F : log2 n −→ 2)) = O(1)

where F describes n in binary.
Considering numbers as such triples, we have the following theorem:
Theorem 8 Any partially computable function of natural numbers can be computed with Sammy.
Proof. We prove that Sammy can perform the initial functions, recursion, composition, and the µ-minimization operator. The zero function is achieved by
simply setting Pe = Pb . The successor of n is achieved by simply composing
with 2. The projection function is simply a Sammy program that accepts n inputs and outputs one of the inputs. Recursion can be done by iteration: we loop
through a number until a pointer reaches Pe . Composition is simply composition
of Sammy programs. µ-minimization is done by doing a loop along N the ordered
category of all natural numbers. QED.
What about complexity theory? In [6] it is shown that categories and functors
can mimic a Turing machine. For every rule of a Turing machine there is a set
amount of steps of a Sammy program. Hence our programming language can
do whatever a Turing machines can do. The size of the Sammy program is, up
to a constant, the same as the number of rules in the Turing machine. That is
KSammy (Fs ) = O(KClassical (s)) where Fs is a functor that describes a string. In
a sense, this says that our Kolmogorov complexity is a generalization of classical
Kolmogorov complexity.
We do not see why there should be a theorem that goes the other way. In
other words, we do not think that a Turing machine can mimic an arbitrary
Sammy program. If, in fact there are some categorical constructions that can
be constructed by a Sammy program, but cannot be constructed by a Turing
machine, then our Kolmogorov complexity is stronger than classical Kolmogorov
complexity theory. Here is an example of a category and a functor that can
NOT be constructed by a Turing machine but might be able to be constructed
by a Sammy program. Let Halt be a the “halting category” whose objects are
the natural numbers and whose morphisms are defined below. Similarly there
is the “halting functor’, H, from N, the totally ordered category of the natural
numbers, to 2, the category with two objects and a unique isomorphism between

them, is defined on the right.

HomHalt (n, n) =





ω


 Id

n

: if ϕn (n) ↓

H(n) =

: if ϕn (n) ↑



 1 : if ϕn (n) ↓

 0 : if ϕ (n) ↑
n

Although, at present time, I do not know how to write a Sammy program to make
such constructions, I believe that using infinite limits and colimits one should
be able to build a type of infinite-time Turing machine to tell if regular Turing
machines will halt or not. (However we are hesitant about making any conjectures. There is an interesting information-theoretic proof of the undecidability
of the halting problem given on page 362 of [1]. Much work remains.)
Although we suspect that Sammy can actually program a larger class of functions than a Turing machine, however, there are some categorical constructions
that are not programmable by Sammy (or any other language.) It is known that
KClassical : Strings −→ N is not a computable function. What about KSammy ?
First let us be careful about the definition of KSammy . It is a function that assigns to every category, functor, and natural transformation a natural number.
We might as well assume that it only assigns natural transformations since identity natural transformations are simply functors and identity functors are simply
categories. Let us think of Cat as the discrete category of natural transformation. We are going to forget the (two) composition structures on Cat because
KSammy does not behave well in terms of composition. So we have a functor
KSammy : Cat −→ N. We prove that this functor is not constructible. The proof
is a self-reference argument similar to the Berry paradox.
Theorem 9 KSammy : Cat −→ N is not constructible.
Proof. Assume (wrongly) that K = KSammy is, in fact, constructible, then
there is a shortest program that describes K. In that case we can ask for the
value of K(K) (this is the core of self reference!). Let K(K) = c. Also, let n be
a natural number and let Pn : 1 −→ N be a functor such that Pn (0) = n. Now
use K and and Pn to construct the following pullback:
Catn 



/ Cat
K



Pn ↓ N


/ N.

Pn ↓ N is the sub-total order of natural numbers that start at n. Catn is the
discrete set of natural transformations whose shortest program is greater than or
equal to n operations. This pullback only needed a few more operations than c.
Say that K(Catn |n) = c′ . However we can “hardwire” any n into the program.
If we do that, we get K(Catn ) = c′ + log n. Choose an n such that n >>
c′ + log n. Then Catn contains objects that require n or more lines of code while
we just described Catn in c′ + log n lines of code. This is like a Berry sentence.
Contradiction! The only thing assumed is that K was constructible. It is not
constructible. QED.
We see this paper as just the beginning of a larger project to understand
the complexity of categorical structures. Our work is far from done. With this
notion of Kolmogorov complexity we get different notions of randomness, compressibility, and different notions of information. We would like to find upper
bounds on some given categorical structures. We also would like to better clarify what is constructible and what is not. Another goal is to continue finding
different categorical versions of the incompleteness theorems. We also would like
to study different complexity measures. Rather than asking what is the shortest
program that produces a categorical structure, we can ask how much time/space
does a program take to create a certain structure. That is, what is the computational complexity of a structure. We can ask how much time does it take for the
shortest program to produce that structure (logical depth.) All these measures
induce hierarchies and classifications of categorical structures. There are also
many other areas that we plan on studying. Here are a few.
There is a relationship between classical Kolmogorov complexity and Shannon’s complexity theory. We would like to formulate a notion of Shannon’s complexity theory for categories. There should be a definition of entropy of a category
which should measure how rigid or flexible categorical structure is. Let C be a
category, then Aut(C) is the group of automorphism functors F : C −→ C. Define the “entropy” (or “Hartley entropy”) of C as H(C) = Log2 |Aut(C)|. Just
as there is a relationship between these measures for strings, there should be a
relationship for categorical structures.
So far we have restricted to classical categories, functors, and natural transformations. What about categories with more structure? For example, what
can we say about a category that we know has all limits and colimits? What
about enriched categories, higher categories, categories with structure, quasicategories, etc? These different structures have been applied in almost every

area of mathematics, computer science and theoretical physics. What we worked
out above is only the first step. Such a study would be extremely interesting to
shed some light on coherence theory. In this paper we saw that a pivotal fact of
the Kolmogorov complexity of categories is that some categories are defined up
to a unique isomorphism. Coherence theory generalizes such notions and is, in
a sense, a higher dimensional version of uniqueness We will learn much about
categorical information content and coherence theory by seeing the way they
interact.
This work should also be related to the important work in quantum information theory. We would like to study some of the physical and mathematical
structures that occur in quantum mechanics with the developed Kolmogorov
complexity tools.
Another area that we would like to explore is Occams razor [5]. This is usually
seen as a criteria in which to judge different physical theories. In short, physicists
formulate functors F :“Physical Phenomena” −→ “Mathematical Structure.”
Universality of the theory demands that “Physical Phenomena” be as large as
possible. In contrast, Occam’s razor demands that “Mathematical Structure”
have low informational content. We would like to use Kolmogorov complexity
on both of these types of categories and the functors that relates them. We feel
that with a better understanding of this we would be able to understand the
question of why it seems that Occam’s razor works so well.

References
1. Calude, Cristian, Information and Randomness: An Algorithmic Perspective Second Edition Springer-Verlag New York, 2002.
2. Hagino, Tatsuya, A Categorical Programming Language, available at
http://voxoz.com/publications/cat/Category
3. Rydeheard, D.E., and Burstall, R.M., Computational Category Theory available
at http://www.cs.man.ac.uk/∼david/categories/book/book.pdf
4. Li, Ming and Vitányi, Paul M. B. An Introduction to Kolmogorov Complexity and
its Applications. Second Edition. Springer, 1997.
5. Yanofsky, N.S., The Outer Limits of Reason: What Science, Mathematics, and
Logic Cannot Tell Us. MIT Press, 2013.
6. Yanofsky, N.S., “Algorithmic Information Theory in Categorical Algebra” work in
progress.

