PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

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:
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