Bases for two weak reducibilities
Johanna Franklin
Hofstra University
While the standard Turing reduction is the main tool recursion theorists use to compare the computational strength of two sets, comparisons of other types of computational strength give rise to other reducibilities. Many of these reducibilities arise from the study of algorithmic randomness and are strictly weaker than Turing reducibility. In this talk, I will focus on two of these reducibilities, JT– and LR-reducibility, and study them through the lens of sets that avoid being random in a very strong way.
A base for randomness is a set A that is Turing computable from some A-random set Z. We can extend this concept to reducibilities other than the standard Turing reducibility: given a weak reducibility ≤W, we say that a set A is a W-base for randomness if A ≤W Z for some A-random set Z. I will fully characterize the JT-bases for randomness and partially characterize the LR-bases for randomness.
This work is joint with Keng Meng Ng and Reed Solomon.
Prof. Franklin has been an Assistant Professor in the mathematics department of Hofstra University since 2014. She studies algorithmic randomness and recursion theory, with applications in probability and ergodic theory. She received her doctorate from the University of California-Berkeley, under the supervision of Ted Slaman, and has taught at the University of Connecticut, Dartmouth College, the University of Waterloo, and the National University of Singapore.