Authors : ... (Author of the conference)
... (Publisher )
Abstract :
I will discuss two recent interactions of the field called randomness via algorithmic tests. With Yokoyama and Triplett, I study the reverse mathematical strength of two results of analysis. (1) The Jordan decomposition theorem says that every function of bounded variation is the difference of two nondecreasing functions. This is equivalent to ACA or to WKL, depending on the formalisation. (2) A theorem of Lebesgue states that each function of bounded variation is differentiable almost everywhere. This turns out to be equivalent WWKL (with some fine work left to be done on the amount of induction needed). The Gamma operator maps Turing degrees to real numbers; a smaller value means a higher complexity. This operator has an analog in the field of cardinal characteristics along the lines of the Rupprecht correspondence [4]; also see [1]. Given a real p between 0 and 1/2, d(p) is the least size of a set G so that for each set x of natural numbers, there is a set y in G such that x and y agree on asymptotically more than p of the bits. Clearly, d is monotonic. Based on Monin's recent solution to the Gamma question (see [3] for background, and the post in [2] for a sketch), I will discuss the result with J. Brendle that the cardinal d(p) doesn't depend on p. Remaining open questions in computability (is weakly Schnorr engulfing equivalent to "Gamma = 0"?) nicely match open questions about these cardinal characteristics.
MSC Codes :
03D25
- Recursively enumerable sets and degrees
03F60
- Constructive and recursive analysis
68Q30
- Algorithmic information theory (Kolmogorov complexity, etc.)
03D32
- Algorithmic randomness and dimension
Language : English
Available date : 07/07/2016
Conference Date : 23/06/2016
Subseries : Research talks
arXiv category : Computer Science ; Logic
Mathematical Area(s) : Logic and Foundations ; Computer Science
Format : MP4 (.mp4) - HD
Video Time : 00:41:43
Targeted Audience : Researchers
Download : https://videos.cirm-math.fr/2016-06-23_Nies.mp4
|
Event Title : Computability, randomness and applications / Calculabilité, hasard et leurs applications Dates : 20/06/2016 - 24/06/2016
Event Year : 2016
Event URL : http://conferences.cirm-math.fr/1408.html
DOI : 10.24350/CIRM.V.19007003
Cite this video as:
(2016). Randomness connecting to set theory and to reverse mathematics. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19007003
URI : http://dx.doi.org/10.24350/CIRM.V.19007003
|
See Also
Bibliography
- [1] Brendle, J., Brooke-Taylor, A., Ng, K.M., & Nies, A. (2013). An analogy between cardinal characteristics and highness properties of oracles. In X. Zhao, Q. Feng, B. Kim, & L. Yu (Eds.), Proceedings of the 13th Asian Logic Conference (pp. 1–28). Singapore: World Scientific - http://www.worldscientific.com/worldscibooks/10.1142/9596
- [2] Nies, A. Logic Blog 2016. In cs.auckland.ac.nz/?nies - https://www.cs.auckland.ac.nz/~nies/
- [3] Monin, B., & Nies, A. (2015). A unifying approach to the Gamma question. In Proceedings of the 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (pp. 585-596). Washington: IEEE press - http://dx.doi.org/10.1109/LICS.2015.60
- [4] Rupprecht, N. Effective correspondents to cardinal characteristics in Cicho?'s diagram. PhD thesis. Ann Arbor: University of Michigan, 2010 - http://hdl.handle.net/2027.42/77915