Kolmogorov Complexity of Categories
Kolmogorov Complexity of Categories
复制标题
柯尔莫哥洛夫范畴的复杂性
DOI：
10.1007/978-3-642-38164-5_25
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
N. Yanofsky
中科院分区：
文献类型：
--
作者：
N. Yanofsky
Kolmogorov复杂性理论用于说明字符串的算法信息内容是什么。它被定义为描述字符串的最短程序的长度。我们提出了一种可用于描述类别、函子和自然变换的编程语言。有了这个，我们将这些分类结构的信息内容定义为描述这些结构的最短程序。给出了我们定义的一些基本结果，包括等价范畴具有相等的柯尔莫哥洛夫复杂度这一事实。我们还证明了不同的定理，关于什么可以用编程语言描述，什么不能用编程语言描述。
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.