Mathieu Hoyrup
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Mathieu Hoyrup has a total of 10 co-authors. Here are the top co-authors by number of shared publications:
- Alexander Shen
LIRMM, Univ Montpellier, CNRS
2 shared publications - Cristóbal Rojas
Departamento de Matemáticas, Universidad Andres Bello, República 220, Santiago, Chile
2 shared publications - Klaus Weihrauch
Fern Universität Hagen
2 shared publications - Laurent Bienvenu
LIAFA CNRS Université de Paris 7 France
2 shared publications - Adam R. Day
SCHOOL OF MATHEMATICS, STATISTICS AND OPERATIONS RESEARCH VICTORIA UNIVERSITY OF WELLINGTON WELLINGTON, NEW ZEALAND
1 shared publication - Cristobal Rojas
University of Toronto, Bahen Centre
1 shared publication
Latest Publications
- 9 December 2016
- Published by Springer Nature in Theory of Computing Systems
- Vol. 60 (3) , 396-420
Genericity of Weakly Computable Objects
- 9 December 2016
- Published by Springer Nature in Theory of Computing Systems
- Vol. 60 (3) , 396-420
Genericity of Weakly Computable Objects
- 1 January 2012
- Published by SAGE Publications in Computability
- Vol. 1 (1) , 3-13
Computability of the Radon-Nikodym Derivative
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 i
- 1 January 2012
- Published by SAGE Publications in Computability
- Vol. 1 (1) , 3-13
Computability of the Radon-Nikodym Derivative
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 i
- Open Access
Computability of the Radon-Nikodym derivative
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.
Open AccessComputability of the Radon-Nikodym derivative
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.
- 16 October 2011
- Published by Pleiades Publishing Ltd in Proceedings of the Steklov Institute of Mathematics
- Vol. 274 (1) , 34-89
Algorithmic tests and randomness with respect to a class of measures
This paper offers some new results on randomness with respect to classes of measures, along with a didactic exposition of their context based on results that appeared elsewhere. We start with the reformulation of the Martin-Löf definition of randomness (with respect to computable measures) in terms of randomness deficiency functions. A formula that expresses the randomness deficiency in terms of prefix complexity is given (in two forms). Some approaches that go in another direction (from deficiency to complexity) are considered. The notion of Bernoulli randomness (independent coin tosses for an asymmetric coin with some probability p of head) is defined. It is shown that a sequence is Bernoulli if it is random with respect to some Bernoulli measure B p . A notion of “uniform test” for Bernoulli sequences is introduced which allows a quantitative strengthening of this result. Uniform tests are then generalized to arbitrary measures. Bernoulli measures B p have the important property that p can be recovered from each random sequence of B p . The paper studies some important consequences of this orthogonality property (as well as most other questions mentioned above) also in the more general setting of constructive metric spaces.
- 16 October 2011
- Published by Pleiades Publishing Ltd in Proceedings of the Steklov Institute of Mathematics
- Vol. 274 (1) , 34-89
Algorithmic tests and randomness with respect to a class of measures
This paper offers some new results on randomness with respect to classes of measures, along with a didactic exposition of their context based on results that appeared elsewhere. We start with the reformulation of the Martin-Löf definition of randomness (with respect to computable measures) in terms of randomness deficiency functions. A formula that expresses the randomness deficiency in terms of prefix complexity is given (in two forms). Some approaches that go in another direction (from deficiency to complexity) are considered. The notion of Bernoulli randomness (independent coin tosses for an asymmetric coin with some probability p of head) is defined. It is shown that a sequence is Bernoulli if it is random with respect to some Bernoulli measure B p . A notion of “uniform test” for Bernoulli sequences is introduced which allows a quantitative strengthening of this result. Uniform tests are then generalized to arbitrary measures. Bernoulli measures B p have the important property that p can be recovered from each random sequence of B p . The paper studies some important consequences of this orthogonality property (as well as most other questions mentioned above) also in the more general setting of constructive metric spaces.
- Open Access
A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points
A theorem of Ku\v{c}era states that given a Martin-L\"of random infinite binary sequence {\omega} and an effectively open set A of measure less than 1, some tail of {\omega} is not in A. We first prove several results in the same spirit and generalize them via an effective version of a weak form of Birkhoff's ergodic theorem. We then use this result to get a stronger form of it, namely a very general effective version of Birkhoff's ergodic theorem, which improves all the results previously obtained in this direction, in particular those of V'Yugin, Nandakumar and Hoyrup, Rojas.
Open AccessA constructive version of Birkhoff's ergodic theorem for Martin-Löf random points
A theorem of Ku\v{c}era states that given a Martin-L\"of random infinite binary sequence {\omega} and an effectively open set A of measure less than 1, some tail of {\omega} is not in A. We first prove several results in the same spirit and generalize them via an effective version of a weak form of Birkhoff's ergodic theorem. We then use this result to get a stronger form of it, namely a very general effective version of Birkhoff's ergodic theorem, which improves all the results previously obtained in this direction, in particular those of V'Yugin, Nandakumar and Hoyrup, Rojas.
- Open Access
- 1 January 2011
- Published by American Institute of Mathematical Sciences (AIMS) in Discrete and Continuous Dynamical Systems
- Vol. 31 (1) , 193-212
Dynamics and abstract computability: Computing invariant measures
We consider the question of computing invariant measures from an abstract point of view. Here, computing a measure means finding an algorithm which can output descriptions of the measure up to any precision. We work in a general framework (computable metric spaces) where this problem can be posed precisely. We will find invariant measures as fixed points of the transfer operator. In this case, a general result ensures the computability of isolated fixed points of a computable map. We give general conditions under which the transfer operator is computable on a suitable set. This implies the computability of many "regular enough" invariant measures and among them many physical measures. On the other hand, not all computable dynamical systems have a computable invariant measure. We exhibit two examples of computable dynamics, one having a physical measure which is not computable and one for which no invariant measure is computable, showing some subtlety in this kind of problems.
- 1 January 2011
- Published by American Institute of Mathematical Sciences (AIMS) in Discrete and Continuous Dynamical Systems
- Vol. 31 (1) , 193-212
Open AccessDynamics and abstract computability: Computing invariant measures
We consider the question of computing invariant measures from an abstract point of view. Here, computing a measure means finding an algorithm which can output descriptions of the measure up to any precision. We work in a general framework (computable metric spaces) where this problem can be posed precisely. We will find invariant measures as fixed points of the transfer operator. In this case, a general result ensures the computability of isolated fixed points of a computable map. We give general conditions under which the transfer operator is computable on a suitable set. This implies the computability of many "regular enough" invariant measures and among them many physical measures. On the other hand, not all computable dynamical systems have a computable invariant measure. We exhibit two examples of computable dynamics, one having a physical measure which is not computable and one for which no invariant measure is computable, showing some subtlety in this kind of problems.