Seminar
| Parent Program: | |
|---|---|
| Location: | SLMath: Online/Virtual |
The generic muchnik degrees, introduced by Schweber, give a way of comparing the computability-theoretic content of uncountable structures. Though obscured slightly by the need for some set-theoretic machinery, I hope to highlight how this notion really gives an easy and natural way to talk about computable structure theory for uncountable structures. I will focus on the tool of complexity profiles.
Complexity profiles are a way of measuring, for two structures A generic Muchnik reducible to B, which subsets of A can be defined using B. The complexity profile of A on itself is the natural analog of considering the relatively intrinsically Sigma_k sets in A.
Using complexity profiles, I will compare three generic Muchnik degrees: Cantor space < Baire space < the Borel-complete degree. In particular, I will describe some dichotomy theorems regarding simple expansions of these and describe how to build degrees strictly between them. (Joint work with Joseph S. Miller, Noah Schweber, and Mariya Soskova.)
To participate in this seminar, please register here: https://www.msri.org/seminars/25206
Complexity Profiles And The Generic Muchnik Degree
To participate in this seminar, please register here: https://www.msri.org/seminars/25206
The generic Muchnik degrees, introduced by Schweber, give a way of comparing the computability-theoretic content of uncountable structures. Though obscured slightly by the need for some set-theoretic machinery, I hope to highlight how this notion really gives an easy and natural way to talk about computable structure theory for uncountable structures. I will focus on the tool of complexity profiles.
Complexity profiles are a way of measuring, for two structures A generic Muchnik reducible to B, which subsets of A can be defined using B. The complexity profile of A on itself is the natural analog of considering the relatively intrinsically Sigma_k sets in A.
Using complexity profiles, I will compare three generic Muchnik degrees: Cantor space < Baire space < the Borel-complete degree. In particular, I will describe some dichotomy theorems regarding simple expansions of these and describe how to build degrees strictly between them. (Joint work with Joseph S. Miller, Noah Schweber, and Mariya Soskova.)
No Notes/Supplements UploadedComplexity Profiles And The Generic Muchnik Degree
| H.264 Video | 25190_28688_8494_Complexity_Profiles_and_the_Generic_Muchnik_Degree.mp4 |