论文标题
卵石深度
Pebble-Depth
论文作者
论文摘要
在本文中，我们介绍了基于卵石传感器的贝内特逻辑深度的新公式。该概念是根据有限状态换能器和卵石传感器的角度的最小长度描述前缀描述性复杂性之间的差异定义的。我们的卵石深度概念满足了深度的三个基本特性：即简易序列和随机序列不深，并且存在缓慢的生长定律类型的存在。我们还将卵石深度与基于有限状态传感器，倒数压缩机和Lempel-Ziv $ 78 $压缩算法的其他深度概念进行了比较。我们首先证明，即使没有正常的有限状态深序列，也存在正常的卵石深序列。然后，我们证明存在一个序列，其卵石深度约为$ 1/2 $，而Lempel-Ziv-Depth水平约为$ 0 $。最后，我们显示了一个序列的存在，该序列的卵石深度大约为$ 1 $，而下调深度约为$ 1/2 $。
In this paper we introduce a new formulation of Bennett's logical depth based on pebble transducers. This notion is defined based on the difference between the minimal length descriptional complexity of prefixes of infinite sequences from the perspective of finite-state transducers and pebble transducers. Our notion of pebble-depth satisfies the three fundamental properties of depth: i.e. easy sequences and random sequences are not deep, and the existence of a slow growth law type result. We also compare pebble-depth to other depth notions based on finite-state transducers, pushdown compressors and the Lempel-Ziv $78$ compression algorithm. We first demonstrate that there exists a normal pebble-deep sequence even though there is no normal finite-state-deep sequence. We then show that there exists a sequence which has pebble-depth level of roughly $1/2$ and Lempel-Ziv-depth level of roughly $0$. Finally we show the existence of a sequence which has a pebble-depth level of roughly $1$ and a pushdown-depth level of roughly $1/2$.
