Kolmogorov Complexity Theory over the Reals

Martin Ziegler, Wouter M. Koolen

Research output: Working paper

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).
Original languageUndefined/Unknown
Publication statusUnpublished - 14 Feb 2008

Keywords

  • cs.CC
  • cs.SC
  • F.4.1; F.1.1; E.4; I.1.2; I.1.3

Cite this