首页> 外文会议>Logic, Language, Information and Computation >On Characteristic Constants of Theories Defined by Kolmogorov Complexity
【24h】

On Characteristic Constants of Theories Defined by Kolmogorov Complexity

机译:关于由Kolmogorov复杂度定义的理论的特征常数

获取原文
获取原文并翻译 | 示例
获取外文期刊封面目录资料

摘要

Chaitin discovered that for each formal system T, there exists a constant c such that no sentence of the form K(x) > c is provable in T, where K(x) is the Kolmogorov complexity of x. We call the minimum such c the Chaitin characteristic constant of T, or c_T. There have been discussions about whether it represents the information content or strength of T. Raatikainen tried to reveal the true source of c_T, stating that it is determined by the smallest index of Turing machine which does not halt but we cannot prove this fact in T. We call the index the Raatikainen characteristic constant of T, denoted by r_T. We show that r-T does not necessarily coincide with c_T; for two arithmetical theories T, T' with a II_1-sentence provable in T' but not in T, there is an enumeration of the Turing machines such that r_T < r_(T') and c_T = c_(T') .
机译:Chaitin发现,对于每个形式系统T,都存在一个常数c,使得T中没有可证明形式为K(x)> c的句子,其中K(x)是x的Kolmogorov复杂度。我们称这种最小值为c的Chaitin特征常数T或c_T。已经讨论过它是否代表T的信息内容或强度。Raatikainen试图揭示c_T的真实来源,指出它是由图灵机的最小索引确定的,该最小索引不会停止,但我们无法在T中证明这一事实。我们将索引称为T的Raatikainen特征常数,用r_T表示。我们证明r-T不一定与c_T一致;对于在T'中可证明有II_1句的两个算术理论T,T',但在T中却没有证明,对图灵机进行了枚举,使得r_T

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号