For more information about this meeting, contact Stephen Simpson, Jan Reimann.
| Title: | Partial randomness and strong separations, part 3. |
|---|
| Seminar: | Logic Seminar |
|---|
| Speaker: | Phil Hudelson, Pennsylvania State University |
|---|
| Abstract Link: | http://www.personal.psu.edu/wmh129/abstract_for_logic_seminar.pdf |
|---|
| Abstract: |
|---|
| Algorithmic randomness and Kolmogorov complexity respectively provide recursion-theoretic frameworks for the study of probability theory and information theory. In this talk we will prove a new strong separation for partial randomness concepts. Two partial randomness definitions, pwt-f-random and dwt-f-random, can be characterized in terms of Kolmogorov complexity by generalizations of Schnorr's theorem: X is dwt-f-random if and only if KP(X_n)>f(n)+O(n) for all n, and X is pwt-f-random if and only if KA(X_n)>f(n)+O(n), where KP and KA mean prefix-free and a priori complexity respectively, and X_n means the length n initial segment of X. We will prove using a forcing argument that under suitable conditions on the function f, there is an X such that KP(X_n)>f(n) for all n, but no Y recursive in X satisfies KP(Y_n)>f(n)+2log_2(f(n))+O(1) for all n (also the analogous result for KA). This theorem, which will be published in The Journal of Symbolic Logic, generalizes the theorem of Miller that there exists a Turing degree of effective Hausdorff dimension exactly 1/2. The new theorem also implies that there exists an X of effective Hausdorff dimension 1 which does not compute a Martin-Lof random, a result originally due to Greenberg and Miller. |
Room Reservation Information
| Room Number: | MB315 |
|---|
| Date: | 02 / 12 / 2013 |
|---|
| Time: | 02:30pm - 03:45pm |
|---|
