...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Proceedings of the National Academy of Sciences of the United States of America >ALGEBRAIC ASPECTS OF THE COMPUTABLY ENUMERABLE DEGREES
【24h】

ALGEBRAIC ASPECTS OF THE COMPUTABLY ENUMERABLE DEGREES

机译：可计算数值的代数方面

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

摘要

A set A of nonnegative integers is computably enumerable (c.e.), also called recursively enumerable (r.e.), if there is a computable method to list its elements. The class of sets B which contain the same information as A under Turing computability (less than or equal to(T)) is the (Turing) degree of A, and a degree is c.e. if it contains a c.e. set. The extension of embedding problem for the c.e. degrees R = (R, <, 0, 0') asks, given finite partially ordered sets P subset of or equal to Q with least and greatest elements, whether every embedding of P into R can be extended to an embedding of Q into R. Many of the most significant theorems giving an algebraic insight into R have asserted either extension or nonextension of embeddings. We extend and unify these results and their proofs to produce complete and complementary criteria and techniques to analyze instances of extension and nonextension. We conclude that the full extension of embedding problem is decidable. [References: 19]
机译：如果有一个可计算的方法列出其元素，则一组非负整数A是可计算的（c.e.），也称为递归可计算的（r.e.）。在图灵可计算性下（小于或等于（T））包含与A相同的信息的集合B的类别为A的（图灵）度，度为c.e.如果包含c.e.组。 c.e.的嵌入问题的扩展R =（R，<，0，0'）度，给定有限的有序集合P的子集，其中P等于或等于Q的最小和最大元素，P每次嵌入到R中是否可以扩展为Q到R的嵌入许多对R具有代数见解的最重要定理都断言了嵌入的可扩展性或非可扩展性。我们扩展并统一这些结果及其证明，以产生完整和补充的标准和技术来分析扩展和不扩展实例。我们得出结论，嵌入问题的完全扩展是可以确定的。 [参考：19]

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号