dorsal/arxiv
View SchemaAn extension of Chaitin's halting probability \Omega to a measurement operator in an infinite dimensional quantum system
| Authors | Kohtaro Tadaki |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0407023 |
| URL | https://arxiv.org/abs/quant-ph/0407023 |
| DOI | 10.1002/malq.200410061 |
| Journal | Mathematical Logic Quarterly, Vol.52, 419-438 (2006) |
Abstract
This paper proposes an extension of Chaitin's halting probability \Omega to a measurement operator in an infinite dimensional quantum system. Chaitin's \Omega 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 -log_2 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 \Omega numbers by universal probabilities. Then, based on this characterization, we propose to define an extension of \Omega 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.
{
"annotation_id": "67637e5e-8994-4223-b1b8-1245ce64acd5",
"date_created": "2026-03-02T18:02:10.278000Z",
"date_modified": "2026-03-02T18:02:10.278000Z",
"file_hash": "ee014d7fbc2558dc4f5f2dd0085a055e7a9c6f01a8dc50cc74c6ec41985215d9",
"private": false,
"record": {
"abstract": "This paper proposes an extension of Chaitin\u0027s halting probability \\Omega to a\nmeasurement operator in an infinite dimensional quantum system. Chaitin\u0027s\n\\Omega is defined as the probability that the universal self-delimiting Turing\nmachine U halts, and plays a central role in the development of algorithmic\ninformation theory. In the theory, there are two equivalent ways to define the\nprogram-size complexity H(s) of a given finite binary string s. In the standard\nway, H(s) is defined as the length of the shortest input string for U to output\ns. In the other way, the so-called universal probability m is introduced first,\nand then H(s) is defined as -log_2 m(s) without reference to the concept of\nprogram-size.\n Mathematically, the statistics of outcomes in a quantum measurement are\ndescribed by a positive operator-valued measure (POVM) in the most general\nsetting. Based on the theory of computability structures on a Banach space\ndeveloped by Pour-El and Richards, we extend the universal probability to an\nanalogue of POVM in an infinite dimensional quantum system, called a universal\nsemi-POVM. We also give another characterization of Chaitin\u0027s \\Omega numbers by\nuniversal probabilities. Then, based on this characterization, we propose to\ndefine an extension of \\Omega as a sum of the POVM elements of a universal\nsemi-POVM. The validity of this definition is discussed.\n In what follows, we introduce an operator version \\hat{H}(s) of H(s) in a\nHilbert space of infinite dimension using a universal semi-POVM, and study its\nproperties.",
"arxiv_id": "quant-ph/0407023",
"authors": [
"Kohtaro Tadaki"
],
"categories": [
"quant-ph",
"cs.CC"
],
"doi": "10.1002/malq.200410061",
"journal_ref": "Mathematical Logic Quarterly, Vol.52, 419-438 (2006)",
"title": "An extension of Chaitin\u0027s halting probability \\Omega to a measurement operator in an infinite dimensional quantum system",
"url": "https://arxiv.org/abs/quant-ph/0407023"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "cf1f2aa0-cae3-409a-ae2a-a9c0c95cd1a0",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}