• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Conference on Computability in Europe(CiE 2005); 20050608-12; Amsterdam(NL) >The Church-Turing Thesis: Breaking the Myth
【24h】

The Church-Turing Thesis: Breaking the Myth

机译：教会图论论题：打破神话

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

摘要

According to the interactive view of computation, communication happens during the computation, not before or after it. This approach, distinct from concurrency theory and the theory of computation, represents a paradigm shift that changes our understanding of what is computation and how it is modeled. Interaction machines extend Turing machines with interaction to capture the behavior of concurrent systems, promising to bridge these two fields. This promise is hindered by the widespread belief, incorrectly known as the Church-Turing thesis, that no model of computation more expressive than Turing machines can exist. Yet Turing's original thesis only refers to the computation of functions and explicitly excludes other computational paradigms such as interaction. In this paper, we identify and analyze the historical reasons for this widespread belief. Only by accepting that it is false can we begin to properly investigate formal models of interaction machines. We conclude the paper by presenting one such model, Persistent Turing Machines (PTMs). PTMs capture sequential interaction, which is a limited form of concurrency; they allow us to formulate the Sequential Interaction Thesis, going beyond the expressiveness of Turing machines and of the Church-Turing thesis.
机译：根据交互的计算观点，通信发生在计算期间，而不是在计算之前或之后。这种与并发理论和计算理论不同的方法代表了一种范式转变，它改变了我们对什么是计算以及如何建模的理解。交互机器通过交互来扩展图灵机，以捕获并发系统的行为，从而有望在这两个领域之间架起桥梁。人们普遍认为，不存在比图灵机更具表达能力的计算模型，这被错误地称为“ Church-Turing”论题所阻碍。然而，图灵的原始论文仅涉及函数的计算，并明确排除了诸如交互之类的其他计算范式。在本文中，我们确定并分析了这种广泛信仰的历史原因。只有接受它是错误的，我们才能开始适当地研究交互机器的形式模型。我们通过介绍一种这样的模型（持久性图灵机（PTM））来结束本文。 PTM捕获顺序交互，这是有限的并发形式。它们使我们能够制定顺序互动论题，超越了图灵机和教会图灵论题的表现力。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号