Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

On the Information Carried by Programs About the Objects they Compute

Mathieu Hoyrup 1 Cristóbal Rojas 2 
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : 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 [8], including complete proofs and a new result (Theorem 9).
Document type :
Journal articles
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Mathieu Hoyrup Connect in order to contact the contributor
Submitted on : Friday, December 9, 2016 - 12:01:47 PM
Last modification on : Friday, January 21, 2022 - 3:13:13 AM
Long-term archiving on: : Thursday, March 23, 2017 - 9:43:47 AM


Files produced by the author(s)



Mathieu Hoyrup, Cristóbal Rojas. On the Information Carried by Programs About the Objects they Compute. Theory of Computing Systems, Springer Verlag, 2017, ⟨10.1007/s00224-016-9726-9⟩. ⟨hal-01413066⟩



Record views


Files downloads