Discrete and Continuous Dynamical Systems · 2010 · 49 citations · 28 references
Natural SciencesComputer ScienceMathematicsAlgorithmsDynamical SystemsTheory Of ComputationComputability TheoryFixed PointsInvariant TheoryComputabilityConditionsInvariant MeasuresInvariant Sets
We consider the question of computing invariant measures from an abstractpoint of view. Here, computing a measure means finding an algorithm which canoutput 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.
28
Computability on subsets of metric spaces
Vasco Brattka, Gero Presser · Theoretical Computer Science · 2003 · 163 citations