(panoramic photo of Moscow from moscow.photobase.ru)
CCR Logo        

Eighth International Conference on Computability, Complexity and Randomness (CCR 2013)

September 23–27, 2013, Moscow, Russia


Classifying principles by the no randomized algorithm property

Ludovic Patey
A principle P studied in reverse mathematics has the no randomized algorithm (NRA) property if when picking a sequence of X_i at random, and considering the omega-model M consisting of the reals which are computable from some nite join of the X_i, then the probability that M is a model of P is zero. We provide a classication of every principle of the current reverse mathematics zoo in terms of the NRA property by providing proofs of NRA property for very weak principles in the zoo. This provides easy separation results like rainbow Ramsey theorem for pairs (RRT22)) implies neither the stable version of thin set for pairs (STS(2)) nor the stable version of Erd}os Moser theorem (SEM).