PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Becky Halpenny.

Title:"Partial randomness and Kolmogorov complexity"
Seminar:Ph.D. Thesis Defense
Speaker:Phil Hudelson; Adviser: Stephen Simpson, Penn State
Abstract Link:
Algorithmic randomness and Kolmogorov complexity provide a computational framework for the study of probability theory and information theory. In this dissertation we prove some theorems about partial randomness. Ten notions of partial randomness are considered, based on the definition of Martin-Lof randomness and its equivalents. Under suitable hypotheses every variant of partial randomness can be defined in terms of either a priori or prefix-free complexity, using a strengthening of Schnorr's theorem. In addition, using Kolmogorov complexity arguments we can weakly separate various notions of partial randomness. For example, under suitable conditions on the function f, there exists an X such that KP(X_n)>f(n) for all n but KP(X_n)=f(n)+O(1) infinitely often. A similar result holds with KP replaced by KA. Here KP and KA denote prefix-free and a priori complexity respectively, X is an infinite sequence of 0's and 1's, and X_n is the length n initial segment of X. A major new theorem is that under suitable conditions on 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 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:MB113
Date:02 / 11 / 2013
Time:04:00pm - 06:30pm