This paper proposes an extension of Chaitin's halting probability 0to measurement operator in
aan infinite dimensional quantum system.Chaitin's
Ω is defined as the probability that the universal self-delimiting Turing machine
U halts, and plays acentral role in the development of algorithmic information theory.Iri the theory, there are two equivalent ways to define the program-size complexity
H(s) of agiven finite binary string
s .In the standard way,
H(s) is defined as the length of the shortest input string for
U to output 8.In the other way, the s0-called universal probability
ΠL is introduced first, and then
H(s) is defined as
−log2m(IF) without reference to the concept of program-size.Mathematically, the statistics of outcomes in aquantum measurement are described by apositive operator-valued measure (POVM) in the most general setting.Based on the theory of computability structures on aBanach space developed by Pour-El and Richards, we extend the universal probability to an analogue of POVM in an infinite dimensional quantum system, called universal semi-POVM.We also give another characterization of Chaitin's
Ω numbers by universal probabilities.Then, based on this characterization, we propose to define an extension of
Ω as asum of the POVM elements of auniversal semi-POVM.The validity of this definition is discussed.1Introduction Algorithmic information theory is afiamework to apply information-theoretic and probabilistic ideas to recursive function theory.One of the primary concepts of algorithmic information theory is the program-size
compl6ffi˙∈y (or Kolmogorov complez-
i˙ty)H{s ) of afinite binary string
s , which is defined as the length of the shortest binary input
Abstract This paper proposes an extension of Chaitin's halting probability Ω to a measurement operator in an infinite dimensional quantum system. Chaitin's Ω is defined as the probability that the universal self‐delimiting Turing machine U halts, and plays a central role in the development of algorithmic information theory. In the theory, there are two equivalent ways to define the program‐size complexity H (s) of a given finite binary string s. In the standard way, H (s) is defined as the length of the shortest input string for U to output s. In the other way, the so‐called universal probability m is introduced first, and then H (s) is defined as –log2 m (s) without reference to the concept of program‐size. Mathematically, the statistics of outcomes in a quantum measurement are described by a positive operator‐valued measure (POVM) in the most general setting. Based on the theory of computability structures on a Banach space developed by Pour‐El and Richards, we extend the universal probability to an analogue of POVM in an infinite dimensional quantum system, called a universal semi‐POVM. We also give another characterization of Chaitin's Ω numbers by universal probabilities. Then, based on this characterization, we propose to define an extension of Ω as a sum of the POVM elements of a universal semi‐POVM. The validity of this definition is discussed. In what follows, we introduce an operator version $ \hat H $(s) of H (s) in a Hilbert space of infinite dimension using a universal semi‐POVM, and study its properties. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)
The origin of the uncertainty inherent in quantum measurements has been discussed since quantum theory's inception, but to date the source of the indeterminacy of measurements performed at an angle with respect to a quantum state's preparation is unknown. Here I propose that quantum uncertainty is a manifestation of the indeterminism inherent in mathematical logic. By explicitly constructing pairs of classical Turing machines that write into each others' program space, I show that the joint state of such a pair is determined, while the state of the individual machine is not, precisely as in quantum measurement. In particular, the eigenstates of the individual machines appear to be superpositions of classical states, albeit with vanishing eigenvalue. Because these "classically entangled" Turing machines essentially implement undecidable "halting problems", this construction suggests that the inevitable randomness that results when interrogating such machines about their state is precisely the randomness inherent in the bits of Chaitin's halting probability. Because this classical construction mirrors quantum measurement, I argue that quantum uncertainty has the same origin.
To explore the limitation of a class of quantum algorithms originally proposed for the Hilbert's tenth problem, we consider two further classes of mathematically non-decidable problems, those of a modified version of the Hilbert's tenth problem and of the computation of the Chaitin's
Ω number, which is a representation of the Gödel's Incompletness theorem. Some interesting connection to Quantum Field Theory is pointed out.