Connecticut CT Logic Seminar

The power of uniformity in algorithmic randomness

Jason Rute (Penn State)

Monday, March 10, 2014 4:45 pm
MSB 203

It is well known that computable analysis and algorithmic randomness are closely connected. Moreover, computable analysis suggests that uniform reducibility should play a large role in algorithmic randomness. In this talk I will show an application of this insight. I will prove a product theorem for Schnorr randomness for non computable measures. This product theorem is an extension of van Lambalgen's well-known theorem. Both the proof and the statement of the theorem rely heavily on uniformity. It also uses computable analysis in important and insightful ways.