On the Gap Between Trivial and Nontrivial Initial Segment Prefix-Free Complexity
文献类型：期刊论文
| 作者 | Baartse, Martijn ; Barmpalias, George |
| 刊名 | THEORY OF COMPUTING SYSTEMS
 |
| 出版日期 | 2013 |
| 卷号 | 52期号:1页码:28-47 |
| 关键词 | Kolmogorov complexity Initial segment prefix-free complexity K-triviality Low for Omega |
| ISSN号 | 1432-4350 |
| 中文摘要 | An infinite sequence X is said to have trivial (prefix-free) initial segment complexity if the prefix-free Kolmogorov complexity of each initial segment of X is the same as the complexity of the sequence of 0s of the same length, up to a constant. We study the gap between the minimum complexity K(0(n)) and the initial segment complexity of a nontrivial sequence, and in particular the nondecreasing unbounded functions f such that K(X (sic)(n)) <= K (0(n)) + f (n) + c for a constant c and all n (*) for a nontrivial sequence X, where K denotes the prefix-free complexity. Our first result is that there exists a Delta(0)(3) unbounded nondecreasing function f which does not have this property. It is known that such functions cannot be Delta(0)(2) hence this is an optimal bound on their arithmetical complexity. Moreover it improves the bound Delta(0)(4) that was known from Csima and Montalban (Proc. Amer. Math. Soc. 134(5): 1499-1502, 2006). Our second result is that if f is Delta(0)(2) then there exists a non-empty Pi(0)(1) class of reals X with nontrivial prefix-free complexity which satisfy (*). This implies that in this case there uncountably many nontrivial reals X satisfying (*) in various well known classes from computability theory and algorithmic randomness; for example low for Omega, non-low for Omega and computably dominated reals. A special case of this result was independently obtained by Bienvenu, Merkle and Nies (STACS, pp. 452-463, 2011). |
| 英文摘要 | An infinite sequence X is said to have trivial (prefix-free) initial segment complexity if the prefix-free Kolmogorov complexity of each initial segment of X is the same as the complexity of the sequence of 0s of the same length, up to a constant. We study the gap between the minimum complexity K(0(n)) and the initial segment complexity of a nontrivial sequence, and in particular the nondecreasing unbounded functions f such that K(X (sic)(n)) <= K (0(n)) + f (n) + c for a constant c and all n (*) for a nontrivial sequence X, where K denotes the prefix-free complexity. Our first result is that there exists a Delta(0)(3) unbounded nondecreasing function f which does not have this property. It is known that such functions cannot be Delta(0)(2) hence this is an optimal bound on their arithmetical complexity. Moreover it improves the bound Delta(0)(4) that was known from Csima and Montalban (Proc. Amer. Math. Soc. 134(5): 1499-1502, 2006). Our second result is that if f is Delta(0)(2) then there exists a non-empty Pi(0)(1) class of reals X with nontrivial prefix-free complexity which satisfy (*). This implies that in this case there uncountably many nontrivial reals X satisfying (*) in various well known classes from computability theory and algorithmic randomness; for example low for Omega, non-low for Omega and computably dominated reals. A special case of this result was independently obtained by Bienvenu, Merkle and Nies (STACS, pp. 452-463, 2011). |
| 收录类别 | SCI |
| 语种 | 英语 |
| WOS记录号 | WOS:000316087100003 |
| 公开日期 | 2014-12-16 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/16700]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 GB/T 7714 | Baartse, Martijn,Barmpalias, George. On the Gap Between Trivial and Nontrivial Initial Segment Prefix-Free Complexity[J]. THEORY OF COMPUTING SYSTEMS,2013,52(1):28-47. |
| APA | Baartse, Martijn,&Barmpalias, George.(2013).On the Gap Between Trivial and Nontrivial Initial Segment Prefix-Free Complexity.THEORY OF COMPUTING SYSTEMS,52(1),28-47. |
| MLA | Baartse, Martijn,et al."On the Gap Between Trivial and Nontrivial Initial Segment Prefix-Free Complexity".THEORY OF COMPUTING SYSTEMS 52.1(2013):28-47. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。