On the Information Carried by Programs About the Objects they Compute

dc.contributor.authorHoyrup, Mathieu
dc.contributor.authorRojas, Cristóbal
dc.date.accessioned2023-11-21T16:57:51Z
dc.date.available2023-11-21T16:57:51Z
dc.date.issued2017-11
dc.descriptionIndexación: Scopuses
dc.description.abstractIn 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). © 2016, Springer Science+Business Media New York.es
dc.description.urihttps://link-springer-com.recursosbiblioteca.unab.cl/article/10.1007/s00224-016-9726-9
dc.identifier.citationTheory of Computing Systems Volume 61, Issue 4, Pages 1214 - 12361 November 2017es
dc.identifier.doi10.1007/s00224-016-9726-9
dc.identifier.issn1432-4350
dc.identifier.urihttps://repositorio.unab.cl/xmlui/handle/ria/54008
dc.language.isoenes
dc.publisherSpringer New York LLCes
dc.rights.licenseCC BY 4.0 DEED
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/deed.es
dc.subjectErshov topologyes
dc.subjectKolmogorov complexityes
dc.subjectMarkov-computablees
dc.subjectRepresentationes
dc.titleOn the Information Carried by Programs About the Objects they Computees
dc.typeArtículoes
Archivos
Bloque original
Mostrando 1 - 1 de 1
Cargando...
Miniatura
Nombre:
LIPIcs.STACS.2015.447.pdf
Tamaño:
647.08 KB
Formato:
Adobe Portable Document Format
Descripción:
TEXTO EN INGLES
Bloque de licencias
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
license.txt
Tamaño:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descripción: