Both the deep theory and connections of algorithmic randomness to other research areas (such as expert algorithms, extractors, measure theory and Hausdorff dimension) has grown tremendously in the past several years. The Kellogg business school at Northwestern just hired a new assistant professor Tai-Wei Hu from Penn State Econ whose job talk paper applies algorithmic randomness that he learned in a logic class from Steve Simpson to understand probability in repeated games.
I've only seen one talk here so far but it was a good one: Alexander Shen showed how to convert many basic questions about Kolmogorov complexity into who wins a certain kind of game.
Unfortunately because of teaching and STOC, I won't be at the workshop long. I've giving a short talk here tomorrow that doesn't directly relate to the topic at hand but kind of a cute not too difficult result: There is a computably enumerable, non-computable oracle A, such that PA-P has no computable sets. Ponder it and I'll post the proof someday when I get it written up.
How come nobody every tells me about these things??
ReplyDeleteHere's how one could construct such an oracle A. For the moment, drop the requirement that A must be computably enumerable (this could be brought back in using a finite injury argument). Let M_1, M_2, ... be a enumeration of polynomial-time machines with oracle A, and let C_1, C_2, ... be the computably enumerable sets. We attempt to satisfy "Requirement R_[e,i]": M_e is not the characteristic function of C_i for every pair [e,i]. For each pair [e,i], search for a string sigma extending the current oracle A_s which witnesses that M_e does not equal the characteristic function for C_i. If such a sigma is found, then set A_{s+1} to be sigma. Otherwise do nothing and look at the next pair [e,i]. This construction can be achieved using a halting set oracle.
If sigma is found then R_[e,i] is satisfied forever. If sigma is not found then the oracle A has no bearing on the output of M_e(x) for large x. In the latter case, M_e must be polynomial-time computable. So either M_e will differ from the characteristic function of every computable set, or else it's polynomial-time computable, as desired.