• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Conference on Computability in Europe(CiE 2005); 20050608-12; Amsterdam(NL) >How to Compare the Power of Computational Models
【24h】

How to Compare the Power of Computational Models

机译：如何比较计算模型的功效

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

摘要

We argue that there is currently no satisfactory general framework for comparing the extensional computational power of arbitrary computational models operating over arbitrary domains. We propose a conceptual framework for comparison, by linking computational models to hypothetical physical devices. Accordingly, we deduce a mathematical notion of relative computational power, allowing the comparison of arbitrary models over arbitrary domains. In addition, we claim that the method commonly used in the literature for "strictly more powerful" is problematic, as it allows for a model to be more powerful than itself. On the positive side, we prove that Turing machines and the recursive functions are "complete" models, in the sense that they are not susceptible to this anomaly, justifying the standard means of showing that a model is "hypercomputational."
机译：我们认为，目前尚没有令人满意的通用框架来比较在任意域上运行的任意计算模型的扩展计算能力。通过将计算模型链接到假设的物理设备，我们提出了一个用于比较的概念框架。因此，我们推导出相对计算能力的数学概念，从而允许在任意域上比较任意模型。此外，我们声称文献中通常使用的“严格更强大”的方法存在问题，因为它允许模型比其自身更强大。从积极的一面，我们证明图灵机和递归函数是“完整的”模型，从某种意义上说，它们不易受此异常影响，这证明了证明模型是“超计算性”的标准方法是正确的。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号