Spectral representation of some computably enumerable sets with an application to quantum provability
Spectral representation of some computably enumerable sets with an application to quantum provability
复制标题
一些可计算可枚举集的谱表示及其在量子可证明性中的应用
DOI：
10.1007/978-3-642-39074-6_6
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
C. S. Calude and K. Tadaki
中科院分区：
文献类型：
--
作者：
Morisada N.;et al.,;C. S. Calude and K. Tadaki
我们提出了一种新型的量子计算机，用于证明一类可计算集合的谱表示。当对形式系统的定理进行编码时，量子计算机通过测量产生形式系统的所有定理和证明。我们猜想谱表示对所有可计算的可枚举集都是有效的。这个猜想意味着，一般形式系统的定理，如Peano算法或ZFC，可以通过测量产生；然而，量子计算机不太可能也能产生证明，就像在特殊情况下。分析表明，展示陈述的可证性与撰写陈述的证明是不同的。
We propose a new type of quantum computer which is used to prove a spectral representation for a classof computable sets. Whencodes the theorems of a formal system, the quantum computer produces through measurement all theorems and proofs of the formal system. We conjecture that the spectral representation is valid for all computably enumerable sets. The conjecture implies that the theorems of a general formal system, like Peano Arithmetic or ZFC, can be produced through measurement; however, it is unlikely that the quantum computer can produce the proofs as well, as in the particular case of. The analysis suggests that showing the provability of a statement is different from writing up the proof of the statement.