Incompleteness and undecidability theorems have to be revised in view of quantum information and computation theory. qrt.tex 1 As has already been pointed out in Gödel’s centennial paper on the incompleteness af arithmetic [1], the classical undecidability theorems of formal logic [2] and the theory of computable functions [4, 5] are based on semantical pardoxes such as the liar [6] or Richard’s paradox. The method of diagonalization, which was first applied by Cantor for a proof of the undenumerability of real numbers [7], has been applied by Turing for a proof of the recursive undecidability of the halting problem [8]. The halting problem is the problem of whether or not an arbitrary algorithm terminates or produces a particular output and terminates. Assume that the halting problem is decidable. Turing [8] proved that this assumption yields a contradiction. To construct the contradiction, consider
Quantum Measurement problem studied in Information Theory approach of systems selfdescription which exploits the information acquisition incompleteness for the arbitrary information system. The studied model of measuring system (MS) consist of measured state S environment E and observer
O processing input S signal.
O considered as the quantum object which interaction with S,E obeys to Schrodinger equation (SE). MS incomplete or restricted states for
O derived by the algebraic QM formalism which exploits Segal and
C∗-algebras. From Segal theorem for systems subalgebras it's shown that such restricted states
VO=∣Oj><Oj∣ describes the classical random 'pointer' outcomes
Oj observed by
O in the individual events. The 'preferred' basis
∣Oj> defined by
O state decoherence via
O - E interactions.
In this work we define an universal arithmetical algorithm, by means of the standard quantum mechanical formalism, called universal qm-arithmetical algorithm. By universal qm-arithmetical algorithm any decidable arithmetical formula (operation) can be decided (realized, calculated. Arithmetic defined by universal qm-arithmetical algorithm called qm-arithmetic one-to-one corresponds to decidable part of the usual arithmetic. We prove that in the qm-arithmetic the undecidable arithmetical formulas (operations) cannot exist (cannot be consistently defined). Or, we prove that qm-arithmetic has no undecidable parts. In this way we show that qm-arithmetic, that holds neither Church's undecidability nor Godel's incompleteness, is decidable and complete. Finally, we suggest that problems of the foundation of the arithmetic, can be solved by qm-arithmetic.