Kolmogorov Complexity Theory over the Reals

M. Ziegler, W.M. Koolen, ArXiv:0802.2027 (2008).

Download
No fulltext has been uploaded.
Preprint | English
Author
Ziegler, Martin; Koolen, Wouter M.
Abstract
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 Montana and Pardo (1998).
Publishing Year
Journal Title
arXiv:0802.2027
LibreCat-ID

Cite this

Ziegler M, Koolen WM. Kolmogorov Complexity Theory over the Reals. arXiv:08022027. Published online 2008.
Ziegler, M., & Koolen, W. M. (2008). Kolmogorov Complexity Theory over the Reals. In arXiv:0802.2027.
@article{Ziegler_Koolen_2008, title={Kolmogorov Complexity Theory over the Reals}, journal={arXiv:0802.2027}, author={Ziegler, Martin and Koolen, Wouter M.}, year={2008} }
Ziegler, Martin, and Wouter M. Koolen. “Kolmogorov Complexity Theory over the Reals.” ArXiv:0802.2027, 2008.
M. Ziegler and W. M. Koolen, “Kolmogorov Complexity Theory over the Reals,” arXiv:0802.2027. 2008.
Ziegler, Martin, and Wouter M. Koolen. “Kolmogorov Complexity Theory over the Reals.” ArXiv:0802.2027, 2008.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar