2008/02/14 by Martin Ziegler, Ziegler, Martin, Wouter M. Koolen +1
Computer Science · #Computational Complexity (cs.CC) #E.4 #F.1.1 #F.4.1 #FOS: Computer and information sciences #I.1.2 #I.1.3 #Symbolic Computation (cs.SC) #cs.CC #cs.SC
paper · pdf · doi:10.48550/arxiv.0802.2027
arxiv created 2008/03/28 · arxiv updated 2009/12/01
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).