Computable measure theory

In mathematics, computable measure theory is the part of computable analysis that deals with effective versions of measure theory. As with measure theory, this topic draws heavily from knowledge in probability theory. It is concerned with determining whether classical theorems used to determine the "size" of a set (in measure theory) can be calculated with a precisely defined algorithm, that is, one suitable for a computer.[1]

The inability of computers to represent all real numbers (especially irrational numbers) exactly can create errors in the calculations of some classical theorems. This error cannot be truly eliminated by just increasing the size of the digits stored, and so, computable measure theory was born as a way to standardize the limits of the computer in the field of measure theory.[2]

As of 2026, computable measure theory is still a relatively new area of study. Therefore, there are still several different approaches and definitions, with no standardized system. However, like computable theory, the work that is being done in the area is being built on top of the foundations set by Alan Turing, Andrzej Grzegorczyk and Daniel Lacombe.[2]

Some other notable contributors include Šanin[3], Ko[4], Edalat[5], Müller[6] and Weihrauch[7].

## References

1. ↑ Mathieu Hoyrup, Jason Rute. Computable Measure Theory and Algorithmic Randomness. Handbook of Computable Analysis, pp.227-270, 2021, 978-3-030-59234-9. ⟨10.1007/978-3-030-59234-9_7⟩. ⟨hal-02938919⟩
2. ↑ 2.0 2.1 Ding, Decheng; Wu, Yongcheng. "Computable Measure Theory". Sino-Germany Project: 1-22. https://imsarchives.nus.edu.sg/oldwww/Programs/infinity/files/ding1.pdf.
3. ↑ N.A. ˇ Sanin, Constructive Real Numbers and Constructive Function Spaces, volume 21 of Translations of Math ematical Monographs. American Mathematical Society, Providence, 1968.
4. ↑ Ker-I Ko. Complexity Theory of Real Functions. Progress in Theoretical Computer Science. Birkh¨ auser, Boston, 1991.
5. ↑ A. Edalat, Dynamical systems, measures, and fractals via domain theory. Information and Computation, 120(1):32–48, 1995.
6. ↑ Norbert Th. M¨ uller. Computability on random variables. Theoretical Computer Science, 219:287–299, 1999.
7. ↑ K. Weihrauch, Computability on the probability measures on the Borel sets of the unit interval. Theoretical Computer Science, 219:421–437, 1999

* Jeremy Avigad (2012), "Inverting the Furstenberg correspondence", Discrete and Continuous Dynamical Systems, Series A, 32, pp. 3421-3431.
* Abbas Edalat (2009), "A computable approach to measure and integration theory", Information and Computation 207:5, pp. 642-659.
* Stephen G. Simpson (2009), Subsystems of second order arithmetic, 2nd ed., Perspectives in Logic, Cambridge University Press. ISBN 978-0-521-88439-6
* Mathieu Hoyrup, Jason Rute. Computable Measure Theory and Algorithmic Randomness. Handbook of Computable Analysis, pp.227-270, 2021, 978-3-030-59234-9. ⟨10.1007/978-3-030-59234-9_7⟩. ⟨hal-02938919⟩

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Computable measure theory. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Computable_measure_theory&oldid=4417034"