数理解析研究所講究録
Chaitin's halting probabiliy Ω and quantum measurements in an infinite dimensional quantum system (計算機科学基礎理論とその応用 研究集会報告集)
孝太郎 只木
Abstract
This paper proposes an extension of Chaitin's halting probability 0to measurement operator in $\mathrm{a}\mathrm{a}\mathrm{n}$ infinite dimensional quantum system.Chaitin's $\Omega$ 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 $\mathrm{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 $\Pi \mathrm{L}$ is introduced first, and then $H(s)$ is defined as $-\log_{2}m(\mathrm{I}\mathrm{F})$ 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 $\Omega$ numbers by universal probabilities.Then, based on this characterization, we propose to define an extension of $\Omega$ 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 $compl_{6\mathrm{f}\mathrm{f}\dot{i}}\not\in y$ (or Kolmogorov complez- $\dot{i}ty)\mathrm{H}\{\mathrm{s}$ ) of afinite binary string $s$ , which is defined as the length of the shortest binary input