Meeting Details

Title: Partial randomness and strong separations, part 2. Logic Seminar Phil Hudelson, Pennsylvania State University http://www.personal.psu.edu/wmh129/abstract_for_logic_seminar.pdf 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 02 / 05 / 2013 02:30pm - 03:45pm