| Algorithmic randomness and Kolmogorov complexity provide a computational framework for the study of probability theory and information theory. In this dissertation we prove the following theorems about partial randomness and complexity.;Fourteen notions of partial randomness are considered: three using generalized Martin-Lof tests, six using generalized Solovay tests, one in terms of martingales, and four using either a priori (KA) or prefix-free (KP) complexity. Under suitable hypotheses, every test or martingale variant of partial randomness can be characterized using either KA or KP, via generalizations of celebrated theorems of Schnorr and Levin. New partial randomness notions are introduced, based on the first Borel-Cantelli lemma; these notions are equivalent to other notions under suitable conditions on f. It is also shown that while effectivizations of the first Borel-Cantelli lemma can be used to characterize Martin-Lof randomness, effectivizations of the second Borel-Cantelli lemma instead characterize Kurtz randomness.;Using complexity arguments we weakly separate notions of partial randomness. Under suitable hypotheses on the function f, there exists an X such that KP(X ↾ n) ≥ f(n) + O(1) for all n but KP(X ↾ n) ≤ f(n) + O(1) infinitely often. A similar result holds with KP replaced by KA. Here 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 hypotheses 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) + 2 log2 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.;X is K-trivial if its initial segment complexity is always minimal, that is KP(X ↾ n) = KP(n) + O(1) for all n. We give a new and simpler proof that no K-trivial can be random relative to a continuous measure. We also show that if X is K-trivial and Y is computable from the halting problem O' then there is no measure mu such that X and Y are mutually relatively mu-random and mu({ X, Y}) = 0. |
