TY - GEN
AB - 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).
AU - Ziegler, Martin
AU - Koolen, Wouter M.
ID - 26235
T2 - arXiv:0802.2027
TI - Kolmogorov Complexity Theory over the Reals
ER -