Algorithmic Aspects of Lipschitz Functions

被引：12

作者：

Freer, Cameron ^{[1
]}

Kjos-Hanssen, Bjorn ^{[2
]}

Nies, Andre ^{[3
]}

Stephan, Frank ^{[4
]}

机构：

[1] MIT, Comp Sci & Artificial Intelligence Lab, Cambridge, MA 02139 USA

[2] Univ Hawaii Manoa, Dept Math, Honolulu, HI 96822 USA

[3] Univ Auckland, Dept Comp Sci, Auckland 1010, New Zealand

[4] Natl Univ Singapore, Dept Math, Singapore 119077, Singapore

来源：

COMPUTABILITY-THE JOURNAL OF THE ASSOCIATION CIE | 2014年 / 3卷 / 01期

基金：

美国国家科学基金会;

关键词：

lipschitz functions; computability;

D O I：

10.3233/COM-14025

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We characterize the variation functions of computable Lipschitz functions. We show that a real z is computably random if and only if every computable Lipschitz function is differentiable at z. Beyond these principal results, we show that a real z is Schnorr random if and only if every Lipschitz function with L-1-computable derivative is differentiable at z.

引用

页码：45 / 61

页数：17

共 23 条

[1]

[Anonymous], 1989, KOLMOGOROV COMPLEXIT

[2]

[Anonymous], 1996, PROBABILITY THEORY E

[3]

Bienvenu L., 2012, MATH FORSCHUNGSINSTI

[4]

Bogachev Vladimir I., 2007, MEASURE THEORY, V2

[5]

Bogachev Vladimir I., 2007, MEASURE THEORY, V1

[6]

Brattka V., RANDOMNESS DIFFERENT

[7]

Carothers N. L., 2000, REAL ANAL

[8]

Demuth O., 1975, COMMENTATIONES MATH, V16

[9]

Downey RG, 2010, THEOR APPL COMPUT, P401, DOI 10.1007/978-0-387-68441-3

[10]

Heinonen J., 2005, REPORT U JYVASKYLA D, V100, P177

← 1 2 3 →