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 |