Spectral representation of some computably enumerable sets with an application to quantum provability

DOI10.1007/978-3-642-39074-6_6zbMATH Open1433.03110arXiv1303.5502OpenAlexW3106027530MaRDI QIDQ5300909FDOQ5300909

Authors: Cristian S. Calude, Kohtaro Tadaki 

Publication date: 28 June 2013

Published in: Unconventional Computation and Natural Computation (Search for Journal in Brave)

Abstract: We propose a new type of quantum computer which is used to prove a spectral representation for a class F of computable sets. When S in F codes 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 F. The analysis suggests that showing the provability of a statement is different from writing up the proof of the statement.

Full work available at URL: https://arxiv.org/abs/1303.5502

Recommendations

• scientific article; zbMATH DE number 6917933
• Mathematical proof
• scientific article; zbMATH DE number 1775174
• Quantum principles and mathematical computability
• Quantum proofs

Mathematics Subject Classification ID

Quantum computation (81P68) Recursively (computably) enumerable sets and degrees (03D25) Turing machines and related notions (03D10) Classical models of computation (Turing machines, etc.) (68Q04)

Cited In (1)

• Title not available (Why is that?)

This page was built for publication: Spectral representation of some computably enumerable sets with an application to quantum provability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300909)