Multi angle

H 1 A derivation on the field of d.c.e.reals

Auteurs : Miller, Joseph (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : Barmpalias and Lewis-Pye recently proved that if $\alpha$ and $\beta$ are (Martin-Löf) random left-c.e. reals with left-c.e. approximations $\{\alpha_s \}_{s \in\ omega}$ and $\{\beta_s \}_{s \in\ omega}$, then
    \frac{\partial\alpha}{\partial\beta} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\beta-\beta_s}.
    converges and is independent of the choice of approximations. Furthermore, they showed that $\partial\alpha/\partial\beta = 1$ if and only if $\alpha-\beta$ is nonrandom; $\partial\alpha/\partial\beta>1$ if and only if $\alpha-\beta$ is a random left-c.e. real; and $\partial\alpha/\partial\beta<1$ if and only if $\alpha-\beta$ is a random right-c.e. real.

    We extend their results to the d.c.e. reals, which clarifies what is happening. The extension is straightforward. Fix a random left-c.e. real $\Omega$ with approximation $\{\Omega_s\}_{s\in\omega}$. If $\alpha$ is a d.c.e. real with d.c.e. approximation $\{\alpha_s\}_{s\in\omega}$, let
    \partial\alpha = \frac{\partial\alpha}{\partial\Omega} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\Omega-\Omega_s}.
    As above, the limit exists and is independent of the choice of approximations. Now $\partial\alpha=0$ if and only if $\alpha$ is nonrandom; $\partial\alpha>0$ if and only if $\alpha$ is a random left-c.e. real; and $\partial\alpha<0$ if and only if $\alpha$ is a random right-c.e. real.

    As we have telegraphed by our choice of notation, $\partial$ is a derivation on the field of d.c.e. reals. In other words, $\partial$ preserves addition and satisfies the Leibniz law:
    \partial(\alpha\beta) = \alpha\,\partial\beta + \beta\,\partial\alpha.
    (However, $\partial$ maps outside of the d.c.e. reals, so it does not make them a differential field.) We will see how the properties of $\partial$ encapsulate much of what we know about randomness in the left-c.e. and d.c.e. reals. We also show that if $f\colon\mathbb{R}\rightarrow\mathbb{R}$ is a computable function that is differentiable at $\alpha$, then $\partial f(\alpha) = f'(\alpha)\,\partial\alpha$. This allows us to apply basic identities from calculus, so for example, $\partial\alpha^n = n\alpha^{n-1}\,\partial\alpha$ and $\partial e^\alpha = e^\alpha\,\partial\alpha$. Since $\partial\Omega=1$, we have $\partial e^\Omega = e^\Omega$.

    Given a derivation on a field, the elements that it maps to zero also form a field: the $ \textit {field of constants}$. In our case, these are the nonrandom d.c.e. reals. We show that, in fact, the nonrandom d.c.e. reals form a $ \textit {real closed field}$. Note that it was not even known that the nonrandom d.c.e. reals are closed under addition, and indeed, it is easy to prove the convergence of [1] from this fact. In contrast, it has long been known that the nonrandom left-c.e. reals are closed under addition (Demuth [2] and Downey, Hirschfeldt, and Nies [3]). While also nontrivial, this fact seems to be easier to prove. Towards understanding this difference, we show that the real closure of the nonrandom left-c.e. reals is strictly smaller than the field of nonrandom d.c.e. reals. In particular, there are nonrandom d.c.e. reals that cannot be written as the difference of nonrandom left-c.e. reals; despite being nonrandom, they carry some kind of intrinsic randomness.

    Codes MSC :
    03D28 - Other Turing degree structures
    03D80 - Applications of computability and recursion theory
    03F60 - Constructive and recursive analysis
    68Q30 - Algorithmic information theory (Kolmogorov complexity, etc.)

      Informations sur la Vidéo

      Langue : Anglais
      Date de publication : 07/07/2016
      Date de captation : 23/06/2016
      Collection : Research talks ; Computer Science ; Logic and Foundations
      Format : MP4
      Durée : 00:52:16
      Domaine : Computer Science ; Logic and Foundations
      Audience : Chercheurs ; Doctorants , Post - Doctorants
      Download : https://videos.cirm-math.fr/2016-06-23_Miller.mp4

    Informations sur la rencontre

    Nom de la rencontre : Computability, randomness and applications / Calculabilité, hasard et leurs applications
    Organisateurs de la rencontre : Bienvenu, Laurent ; Jeandel, Emmanuel ; Porter, Christopher
    Dates : 20/06/16 - 24/06/2016
    Année de la rencontre : 2016
    URL Congrès : http://conferences.cirm-math.fr/1408.html

    Citation Data

    DOI : 10.24350/CIRM.V.19006803
    Cite this video as: Miller, Joseph (2016). A derivation on the field of d.c.e.reals. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19006803
    URI : http://dx.doi.org/10.24350/CIRM.V.19006803

    Voir aussi


    1. 1] Barmpalias, G., & Lewis-Pye, A. (2016). Differences of halting probabilities. - https://arxiv.org/abs/1604.00216

    2. [2] Demut, O. (1975). Constructive pseudonumbers. Commentationes Mathematicae Universitatis Carolinae, 16(2),(1975), 315–331 - http://dml.cz/handle/10338.dmlcz/105626

    3. [3] Downey, R.G., Hirschfeldt, D.R., & Nies, A. (2002). Randomness, computability, and density. SIAM Journal on Computing, 31(4), 1169–1183 - http://dx.doi.org/10.1137/S0097539700376937

Titres de périodiques et e-books électroniques (Depuis le CIRM)

Ressources Electroniques

Books & Print journals

Recherche avancée