Examinando por Autor "Hoyrup, Mathieu"

Mostrando 1 - 3 de 3
  • Miniatura
    Ítem
    Computability of the Radon-Nikodym derivative
    (Pre-print, 2011) Hoyrup, Mathieu; Rojas, Cristóbal; Weihrauch, Klaus
    We study the computational content of the Radon-Nokodym theorem from measure theory in the framework of the representation approach to computable analysis. We define computable measurable spaces and canonical representations of the measures and the integrable functions on such spaces. For functions f, g on represented sets, f is W-reducible to g if f can be computed by applying the function g at most once. Let RN be the Radon-Nikodym operator on the space under consideration and let EC be the non-computable operator mapping every enumeration of a set of natural numbers to its characteristic function. We prove that for every computable measurable space, RN is W-reducible to EC, and we construct a computable measurable space for which EC is W-reducible to RN.
  • Miniatura
    Ítem
    On the Information Carried by Programs About the Objects they Compute
    (Springer New York LLC, 2017-11) Hoyrup, Mathieu; Rojas, Cristóbal
    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). © 2016, Springer Science+Business Media New York.
  • No hay miniatura disponible
    Ítem
    Realizing semicomputable simplices by computable dynamical systems
    (Elsevier B.V., 2022-10-14) Coronel, Daniel; Frank, Alexander; Hoyrup, Mathieu; Rojas, Cristóbal
    We study the computability of the set of invariant measures of a computable dynamical system. It is known to be semicomputable but not computable in general, and we investigate which semicomputable simplices can be realized in this way. We prove that every semicomputable finite-dimensional simplex can be realized, and that every semicomputable finite-dimensional convex set is the projection of the set of invariant measures of a computable dynamical system. In particular, there exists a computable system having exactly two ergodic measures, none of which is computable. Moreover, all the dynamical systems that we build are minimal Cantor systems. © 2022 Elsevier B.V.