m

F Nous contacter

0

Documents  03D80 | enregistrements trouvés : 12

O
     

-A +A

P Q

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 320 p.
ISBN 978-0-8218-1922-7

Contemporary mathematics , 0257

Localisation : Collection 1er étage

application de la calculabilité # arithmétique # arithmétique d"ordre élevé # degré # degré de Turin # ensemble récursivement énumérable # fonction calculable # logique # modèle nonstandard # numération # récurrence # réductibilité # théorie de récurrence # théorie des modèles # théorie descriptive des ensembles

03C57 ; 03D25 ; 03D28 ; 03D30 ; 03D45 ; 03D80 ; 03E15 ; 03E35 ; 03F35 ; 03H15

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 150 p.
ISBN 978-0-8218-3819-8

Contemporary mathematics , 0425

Localisation : Collection 1er étage

logique

03C52 ; 03D25 ; 03D35 ; 03D80 ; 03E05 ; 03E15 ; 03E55 ; 03E60 ; 05C12 ; 52C20

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Computer Science;Logic and Foundations

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
\[
\begin{equation}
\frac{\partial\alpha}{\partial\beta} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\beta-\beta_s}.
\end{equation}
\]
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.
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
\[
\begin{equation}
\frac{\partial\alpha}{\partial\beta} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\beta-\beta_s}.
\end{equation}
\]
converges and is independent of the choice of approximations. Furthermore, they showed that ...

03D28 ; 03D80 ; 03F60 ; 68Q30

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 412 p.

Actualités scientifiques et industrielles , 1317

Localisation : Ouvrage RdC (OUSP)

constructivisation de définition négative # ensemble récursivement énumérable # ensemble universel # fonction calculable # fonction partielle récursive # fonction primitive récursive # fonction universelle # logique mathématique # machine à calculer abstraite # prédicat général récursif # prédicat primitif récursif # prédicat récursivement énumérable # séparation des réels calculables # théorie des ensembles # théorie des fonctions

03D20 ; 03D25 ; 03D80 ; 03Dxx

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.


ISBN 978-3-540-50035-3

Perspectives in mathematical logic

Localisation : Ouvrage RdC (Pour)

analyse mathematique # informatique # logique # physique # theorie de la recursion

03D80 ; 03F60 ; 46Nxx

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 210 p.

McGraw-Hill series in information porcessing and computers

Localisation : Ouvrage RdC (DAVI)

calculabilité # insolubilité # fonction calculable # fonction récursive # machine de Turing # analyse combinatoire # équation diophantienne # 10ème problème de Hilbert

03Dxx ; 03-01 ; 03-02 ; 03D60 ; 03D20 ; 03D10 ; 03D35 ; 03D03 ; 03D40 ; 11D99 ; 03D55 ; 03D25 ; 03D30 ; 03D80

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- xv; 433 p.
ISBN 978-0-19-923076-1

Oxford logic guides , 0051

Localisation : Ouvrage RdC (NIES)

théorie de la recursion # algorithmique # complexité des ensembles # hasard

03D80 ; 68Q30 ; 03-02 ; 68-02

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- xiii; 151 p.
ISBN 978-3-540-68546-3

Algorithms and computation in mathematics , 0023

Localisation : Ouvrage RdC (BRAV)

logique # calcul complexe # théorie de la récursion # ensemble de Julia # modèles de calcul

03D15 ; 03D80 ; 37F10 ; 37F50 ; 65Y20 ; 68Q05 ; 68Q17 ; 03-99

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- xxviii; 855 p.
ISBN 978-0-387-95567-4

Theory and applications of computability

Localisation : Ouvrage RdC (DOWN)

algorithmique # théorie de l'information # informatique #
complexité de Kolmogorov # théorie de la récurrence

03D25 ; 03D30 ; 03D80 ; 68Q30 ; 68-99 ; 03D32

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- viii; 251 p.
ISBN 978-0-387-90743-7

Texts and monographs in computer science

Localisation : Ouvrage RdC (KFOU)

03D60 ; 68N01 ; 03D80 ; 68-02 ; 03-02

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- vii; 203 p.
ISBN 978-0-8218-7392-2

Student mathematical library , 0062

Localisation : Collection 1er étage

théorie de la recursivité # machine de Turing # complexité des calculs # logique de la programmation

03Dxx ; 68Qxx ; 03-01 ; 03D10 ; 03D15 ; 03D60 ; 03D80 ; 03B70 ; 68Q05

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- xv; 214 p.
ISBN 978-981-4612-61-6

Lecture notes series , 0028

Localisation : Ouvrage RdC (HIRS)

ensemble récursif # mathématiques inversées # théorème de Ramsey # ensemble stable # ensemble cohérent # WKL # lemme de König # arbre # ordre # chaîne # ensemble libre # ensemble maigre # ensemble générique # RCA

03-02 ; 03B30 ; 03F35 ; 03D30 ; 03D80 ; 03E05 ; 05D10

... Lire [+]

Z