EUVIMEDEUVIMED entdecken
Crossref

On the Information Carried by Programs About the Objects they Compute

Mathieu Hoyrup, Cristóbal Rojas

Theory of Computing Systems · 2017-11 · 61 (4) · 1214-1236

DOI: 10.1007/s00224-016-9726-9 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Theory of Computing Systems, online erschienen am 09.12.2016. Verfasst von Mathieu Hoyrup und 1 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 23 Literaturangaben. Gefördert von: FONDECYT, BASAL, Inria.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In computability theory and computable analysis, finite programs can compute infinite objects. Such objects can then be represented by finite programs. Can one characterize the additional useful information contained in a program computing an object, as compared to having the object itself? Having a program immediately gives an upper bound on the Kolmogorov complexity of the object, by simply measuring the length of the program, and such an information cannot usually be derived from an infinite representation of the object. We prove that bounding the Kolmogorov complexity of the object is the only additional useful information. Hence we identify the exact relationship between Markov-computability and Type-2-computability. We then use this relationship to obtain several results characterizing the computational and topological structure of Markov-semidecidable sets. This article is an extended version of Hoyrup and Rojas (2015), including complete proofs and a new result (Theorem 9).

Förderung

  • FONDECYT
  • BASAL
  • Inria
  • Universidad Andres Bello

Zitieren

APA

Hoyrup, M., & Rojas, C. (2017). On the Information Carried by Programs About the Objects they Compute. Theory of Computing Systems, 61(4), 1214-1236. https://doi.org/10.1007/s00224-016-9726-9

Vancouver

Hoyrup M, Rojas C. On the Information Carried by Programs About the Objects they Compute. Theory of Computing Systems. 2017;61(4):1214-1236. doi:10.1007/s00224-016-9726-9

BibTeX
@article{Hoyrup2017,
  author = {Hoyrup, Mathieu and Rojas, Cristóbal},
  title = {On the Information Carried by Programs About the Objects they Compute},
  journal = {Theory of Computing Systems},
  year = {2017},
  volume = {61},
  number = {4},
  pages = {1214--1236},
  doi = {10.1007/s00224-016-9726-9}
}
Kostenlos starten →