PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Stephen Simpson.

Title:Randomness and differentiability
Seminar:Logic Seminar
Speaker:Joseph S. Miller, University of Wisconsin
Abstract:
It is a theorem of classical analysis that a function of bounded variation is differentiable almost everywhere. Demuth effectivized this theorem, showing that a real x is Martin-Löf random if and only if every computable function of bounded variation is differentiable at x. (This is related to a result of Noopur Pathak on the Lebesgue Differentiation Theorem.) We consider the differentiability of nondecreasing functions. Call x computably random if no computable betting strategy can win arbitrarily much betting against the bits in the binary expansion of x. We sketch the proof that x is computably random if and only if every nondecreasing computable function is differentiable at x. Because a function has bounded variation iff it is the difference of two nondecreasing functions, this is closely related to Demuth's result, and we are able to derive the harder direction using the fact that x is Martin-Löf random if and only if it is computably random relative to some PA degree. This is joint work with André Nies and Vasco Brattka. All uncommon notions will be reviewed.

Room Reservation Information

Room Number:MB315
Date:03 / 30 / 2010
Time:02:30pm - 03:45pm