Algorithmic Aspects of Lipschitz Functions

Article type: Research Article

Authors: Freer, Cameron | Kjos-Hanssen, Bjø rn | Nies, André | Stephan, Frank

Affiliations: Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology, Cambridge, MA 02139, USA freer@math.mit.edu | Department of Mathematics, University of Hawai̒i at Mānoa, 2500 Campus Rd, Honolulu, HI 96822, USA bjoern@math.hawaii.edu | Department of Computer Science, University of Auckland, Auckland 1010, New Zealandandre@cs.auckland.ac.nz | Department of Mathematics, National University of Singapore, 21 Lower Kent Ridge Road, Singapore 119077 fstephan@comp.nus.edu.sg

Abstract: We characterize the variation functions of computable Lipschitz functions. We show that a real <![CDATA[$z$]] is computably random if and only if every computable Lipschitz function is differentiable at <![CDATA[$z$]]. Beyond these principal results, we show that a real <![CDATA[$z$]] is Schnorr random if and only if every Lipschitz function with <![CDATA[$L_{1}$]]-computable derivative is differentiable at <![CDATA[$z$]].

Keywords: Lipschitz functions, Computability

DOI: 10.3233/COM-14025

Journal: Computability, vol. 3, no. 1, pp. 45-61, 2014