Kolmogorov Complexity Theory over the Reals

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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).

Keywords

Computational Complexity, Symbolic Computation, F.4.1; F.1.1; E.4; I.1.2; I.1.3

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/157533

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0802.2027
 http://arxiv.org/abs/0802.2027

Collections

arXiv