Classical physics and the Church--Turing Thesis
Classical physics and the Church--Turing Thesis
复制标题
经典物理学与教会--图灵论
DOI：
10.1145/602382.602411
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
A. Yao
中科院分区：
文献类型：
--
作者：
A. Yao
物理定律是否允许建造能够比标准计算模型更快地解决某些问题的计算机器？最近的证据表明，量子世界可能就是这种情况。但这个问题即使在经典物理学领域也引起了极大的兴趣。在这篇文章中，我们观察到，有一个基本的紧张局势之间的扩展教会-图灵命题和存在的许多看似棘手的计算问题所产生的经典物理。解决这种不相容性的努力既可以促进我们对计算理论的认识，也可以满足科学计算的需要。
Would physical laws permit the construction of computing machines that are capable of solving some problems much faster than the standard computational model? Recent evidence suggests that this might be the case in the quantum world. But the question is of great interest even in the realm of classical physics. In this article, we observe that there is fundamental tension between the Extended Church--Turing Thesis and the existence of numerous seemingly intractable computational problems arising from classical physics. Efforts to resolve this incompatibility could both advance our knowledge of the theory of computation, as well as serve the needs of scientific computing.