2008-08-21
Kolmogorov complexity theory over the reals
Publication
Publication
Electronic Notes in Theoretical Computer Science p. 153- 169
Kolmogorov Complexity constitutes an integral part of computability theory, information theory, and computational complexity theory—in the discrete setting of bits and Turing machines. Over real numbers, on the other hand, the BSS-machine (aka real-RAM) has been established as a major model of computation. This real realm has turned out to exhibit natural counterparts to many notions and results in classical complexity and recursion theory; although usually with considerably different proofs. The present work investigates similarities and differences between discrete and real Kolmogorov Complexity as introduced by Montaña and Pardo (1998).
| Additional Metadata | |
|---|---|
| , , , | |
| Elsevier | |
| doi.org/10.1016/j.entcs.2008.12.014 | |
| Electronic Notes in Theoretical Computer Science | |
| Discrete, interactive & algorithmic mathematics, algebra and number theory | |
| 5th International Conference on Computability and Complexity in Analysis, CCA 2008 | |
| Organisation | Quantum Computing and Advanced System Research |
|
Ziegler, M., & Koolen-Wijkstra, W. (2008). Kolmogorov complexity theory over the reals. In Proceedings of the 5th International Conference on Computability and Complexity in Analysis, CCA 2008 (pp. 153–169). Elsevier. doi:10.1016/j.entcs.2008.12.014 |
|
