preprint
Kolmogorov Complexity Theory over the Reals
Martin
Ziegler
author
Wouter M.
Koolen
author
63
department
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).
2008
eng
arXiv:0802.2027
Ziegler, Martin, and Wouter M. Koolen. “Kolmogorov Complexity Theory over the Reals.” <i>ArXiv:0802.2027</i>, 2008.
Ziegler, Martin, and Wouter M. Koolen. “Kolmogorov Complexity Theory over the Reals.” <i>ArXiv:0802.2027</i>, 2008.
@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 M, Koolen WM. Kolmogorov Complexity Theory over the Reals. <i>arXiv:08022027</i>. Published online 2008.
Ziegler, M., & Koolen, W. M. (2008). Kolmogorov Complexity Theory over the Reals. In <i>arXiv:0802.2027</i>.
M. Ziegler and W. M. Koolen, “Kolmogorov Complexity Theory over the Reals,” <i>arXiv:0802.2027</i>. 2008.
M. Ziegler, W.M. Koolen, ArXiv:0802.2027 (2008).
262352021-10-15T09:34:19Z2022-01-06T06:57:18Z