文章基本信息

标题：Logical operations and Kolmogorov complexity
本地全文：下载
作者：Alexander Shen ; Nikolai Vereshchagin
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We define Kolmogorov complexity of a set of strings as the minimal Kolmogorov complexity of its element. Consider three logical operations on sets going back to Kolmogorov and Kleene: (A OR B) is the direct sum of A,B, (A AND B) is the cartesian product of A,B, (A --> B) is the set of programs mapping any element of A to an element of B. We find complexity of certain particular sets obtained from singelton sets (e.g. ({x}-->{y})-->{y}).
关键词：Kleene's realizability , Kolmogorov complexity , Pierce law