Effective genericity and differentiability. (English) Zbl 1345.03085
Summary: We prove that a real \(x\) is 1-generic if and only if every differentiable computable function has continuous derivative at \(x\). This provides a counterpart to recent results connecting effective notions of randomness with differentiability. We also consider multiply differentiable computable functions and polynomial time computable functions.
MSC:
| 03D78 | Computation over the reals, computable analysis |
| 03D32 | Algorithmic randomness and dimension |
| 26A21 | Classification of real functions; Baire classification of sets and functions |
| 26A24 | Differentiation (real functions of one variable): general theory, generalized derivatives, mean value theorems |
References:
| [1] | [1] V Brattka, J S Miller, A Nies, Randomness and Differentiability, to appear in Transactions of the AMS |
| [2] | [2] R P Brent,Fast multiple-precision evaluation of elementary functions, Journal of the ACM 23 (1976) 242–251 · Zbl 0324.65018 |
| [3] | [3] A M Bruckner, J L Leonard,Derivatives, The American Mathematical Monthly 73 (1966) 24–56 |
| [4] | [4] O Demuth, The differentiability of constructive functions of weakly bounded variation on pseudo numbers, Commentationes Mathematicae Universitatis Carolinae 16 (1975) 583–599 (In Russian) · Zbl 0325.02023 |
| [5] | [5] R G Downey, D R Hirschfeldt,Algorithmic Randomness and Complexity, Springer (2010) · Zbl 1221.68005 |
| [6] | [6] C Jockusch,Degrees of generic sets, from: ”Recursion theory: its generalisations and applications”, (F R Drake, S S Wainer, editors), London Mathematical Society Lecture Note Series, Cambridge University Press (1980) 110–139 |
| [7] | [7] A S Kechris,Classical Descriptive Set Theory, Springer-Verlag (1995) |
| [8] | [8] K Ko,Complexity theory of real functions, Birkh\"{}auser (1991) · Zbl 0791.03019 |
| [9] | [9] Y N Moschovakis,Descriptive Set Theory, volume 155 of Mathematical Surveys and Monographs, second edition, American Mathematical Society (2009) · Zbl 1154.03025 |
| [10] | [10] P G Odifreddi, Classical Recursion Theory, volume 125 of Studies in Logic and the Foundations of Mathematics, North-Holland (1989) · Zbl 0661.03029 |
| [11] | [11] P G Odifreddi, Classical Recursion Theory: Volume II, volume 143 of Studies in Logic and the Foundations of Mathematics, North-Holland (1999) · Zbl 0931.03057 |
| [12] | [12] J C Oxtoby,Measure and Category, volume 2 of Graduate Texts in Mathematics, second edition, Spinter-Verlag (1980) · Zbl 0435.28011 |
| [13] | [13] M B Pour-El, J I Richards,Computability in Analysis and Physics, volume 1 of Perspectives in Mathematical Logic, Springer-Verlag (1989) · Zbl 0678.03027 |
| [14] | [14] W Rudin, Principles of Mathematical Analysis, third edition, McGraw-Hill Book Company (1976) |
| [15] | [15] K Weihrauch,Computable analysis: an introduction, Springer (2000) Radboud University Nijmegen, Department of Mathematics, P.O. Box 9010, 6500 GL Nijmegen, the Netherlands. r.kuyper@math.ru.nl,terwijn@math.ru.nl Received: 19 November 2013Revised: 20 August 2014 · Zbl 0956.68056 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
