Kolmogorov Complexity Theory over the Reals
| dc.creator | Ziegler, Martin | |
| dc.creator | Koolen, Wouter M. | |
| dc.date | 2008-02-14 | |
| dc.date | 2008-03-28 | |
| dc.date.accessioned | 2026-07-07T09:28:44Z | |
| dc.date.available | 2026-07-07T09:28:44Z | |
| dc.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). | |
| dc.identifier | https://arxiv.org/abs/0802.2027 | |
| dc.identifier | http://arxiv.org/abs/0802.2027 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/157533 | |
| dc.subject | Computational Complexity | |
| dc.subject | Symbolic Computation | |
| dc.subject | F.4.1; F.1.1; E.4; I.1.2; I.1.3 | |
| dc.title | Kolmogorov Complexity Theory over the Reals | |
| dc.type | text |