Upper semilattice of binary strings with the relation "x is simple conditional to y"
Upper semilattice of binary strings with the relation "x is simple conditional to y"
复制标题
二进制串的上半格，其关系为“x 是 y 的简单条件”
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
N. Vereshchagin
中科院分区：
文献类型：
--
作者：
A. Muchnik;Andrei E. Romashchenko;A. Shen;N. Vereshchagin
本文构造了一个结构R，它是图灵度半格的“有限版本”。它的元素是字符串（技术上是字符串序列），x/spl les/y意味着K(x|)=（x相对于y的条件Kolmogorov复杂度）很小。我们在R中构造两个没有最大下界的元素。我们给出了一系列的例子，表明自然代数结构如何给出两个具有下界0（最小元素）但重要互信息的元素。（这类的第一个例子是由Gacs-Korner（1973）使用完全不同的技术构建的。）我们定义了R的一对元素的“复杂度轮廓”的概念，并给出了它在特定情况下的（精确的）上界和下界。
In this paper we construct a structure R that is a "finite version" of the semilattice of Turing degrees. Its elements are strings (technically, sequences of strings) and x/spl les/y means that K(x|)=(conditional Kolmogorov complexity of x relative to y) is small. We construct two elements in R that do not have greatest lower bound. We give a series of examples that show how natural algebraic constructions give two elements that have lower bound O (minimal element) but significant mutual information. (A first example of that kind was constructed by Gacs-Korner (1973) using completely different technique.) We define a notion of "complexity profile" of the pair of elements of R and give (exact) upper and lower bounds for it in a particular case.