• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Conference on Computability in Europe(CiE 2005); 20050608-12; Amsterdam(NL) >The Small Grzegorczyk Classes and the Typed λ-Calculus
【24h】

The Small Grzegorczyk Classes and the Typed λ-Calculus

机译：小Grzegorczyk类和类型λ微积分

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The class Δ_0~N of rudimentary relations and the small relational Grzegorczyk classes ε_*~0, ε_*~1, ε_*~2 attracted fairly much attention during the latter half of the previous century, e.g. Gandy, Paris-Wilkie, and numerous others. Yet, the open problems imposed by these classes are still there for new generations to battle. It is well know, and rather obvious, that Δ_0~N is contained in ε_*~0 is contained in ε_*~1 is contained in ε_*~2, but it is not known whether any of the inclusions are strict, indeed it is open if the inclusion Δ_0~N is contanined in ε_*~2 is strict. It is proved in Bel'tyukov that ε_*~1 = ε_*~2 implies ε_*~0 = ε_*~2. Furthermore, we know that Δ_0~N = ε_*~0 implies Δ_0~N = ε_*~2 (We do not know if this is proved anywhere in the literature, but it will be a corollary of some of the theorems below.). The open problems can be traced back to Grzegorczyk's initial paper from 1953, and it is fair to say that the problems belong to sub-recursion theory, but they are closely related to complexity theory and computer science.
机译：基本关系类Δ_0〜N和小关系Grzegorczyk类ε_*〜0，ε_*〜1，ε_*〜2在上个世纪下半叶引起了相当大的关注。甘迪（Gandy），巴黎·威尔基（Paris-Wilkie）等。然而，这些阶级所施加的开放性问题仍然存在，以供新一代人使用。众所周知，并且很明显，包含在ε_*〜0中的Δ_0〜N包含在包含在ε_*〜2的ε_*〜1中，但是尚不知道任何夹杂物是否严格，实际上如果夹杂物Δ_0〜N被包含在ε_*〜2中是严格的，则打开。在Bel'tyukov中证明ε_*〜1 =ε_*〜2意味着ε_*〜0 =ε_*〜2。此外，我们知道Δ_0〜N =ε_*〜0意味着Δ_0〜N =ε_*〜2（我们不知道是否在文献中对此进行了证明，但这将是下面某些定理的推论。） 。开放的问题可以追溯到1953年Grzegorczyk的最初论文，可以公平地说，这些问题属于子递归理论，但它们与复杂性理论和计算机科学密切相关。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号