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 [email protected] | Department of Mathematics, University of Hawai̒i at Mānoa, 2500 Campus Rd, Honolulu, HI 96822, USA [email protected] | Department of Computer Science, University of Auckland, Auckland 1010, New [email protected] | Department of Mathematics, National University of Singapore, 21 Lower Kent Ridge Road, Singapore 119077 [email protected]

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