Computing the non-computable
Computing the non-computable
复制标题
计算不可计算的
DOI：
10.1080/00107510302712
复制
发表时间：
2002
影响因子：
2
通讯作者：
T. Kieu
中科院分区：
文献类型：
--
作者：
T. Kieu
我们在量子计算的框架中探讨可计算性的概念，它在数学和理论计算机科学中占有中心地位。希尔伯特第十问题的量子算法利用了量子绝热过程，该问题相当于图灵停止问题，已知在数学上不可计算。本文还讨论了其他一些数学上的不可计算问题的广义量子算法。所有这些算法的关键要素是物理观测值和这些值的量子力学概率分布的可测量性。有人认为，可计算性，以及数学的极限，不仅应该由数学本身决定，而且应该由物理原理决定。
We explore in the framework of quantum computation the notion of computability, which holds a central position in mathematics and theoretical computer science. A quantum algorithm that exploits the quantum adiabatic processes is considered for Hilbert's tenth problem, which is equivalent to the Turing halting problem and known to be mathematically non-computable. Generalized quantum algorithms are also considered for some other mathematical non-computables in the same and in different non-computability classes. The key element of all these algorithms is the measurability of both the values of physical observables and the quantum-mechanical probability distributions for these values. It is argued that computability, and thus the limits of mathematics, ought to be determined not solely by mathematics itself but also by physical principles.