m

Documents  03D32 | enregistrements trouvés : 5

O
     

-A +A

P Q

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

Research talks;Computer Science;Logic and Foundations

Recall that normality is a elementary form of randomness: an infinite word is normal to a given alphabet if all blocks of symbols of the same length occur in the word with the same asymptotic frequency. We consider a notion of independence on pairs of infinite words formalising that two words are independent if no one helps to compress the other using one-to-one finite transducers with two inputs. As expected, the set of independent pairs has Lebesgue measure 1. We prove that not only the join of two normal words is normal, but, more generally, the shuffling with a finite transducer of two normal independent words is also a normal word. The converse of this theorem fails: we construct a normal word as the join of two normal words that are not independent. We construct a word x such that the symbol at position n is equal to the symbol at position 2n. Thus, x is the join of x itself and the subsequence of odd positions of x. We also show that selection by finite automata acting on pairs of independent words preserves normality. This is a counterpart version of Agafonov's theorem for finite automata with two input tapes.
This is joint work with Olivier Carton (Universitéé Paris Diderot) and Pablo Ariel Heiber (Universidad de Buenos Aires).
Recall that normality is a elementary form of randomness: an infinite word is normal to a given alphabet if all blocks of symbols of the same length occur in the word with the same asymptotic frequency. We consider a notion of independence on pairs of infinite words formalising that two words are independent if no one helps to compress the other using one-to-one finite transducers with two inputs. As expected, the set of independent pairs has ...

68R15 ; 11K16 ; 03D32

... Lire [+]

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

Research talks;Computer Science;Logic and Foundations

Carleson's Theorem states that for $1 < p < \infty$, the Fourier series of a function $f$ in $L^p[-\pi,\pi]$ converges to $f$ almost everywhere. We consider this theorem in the context of computable analysis and show the following two results.
(1) For a computable $p > 1$, if $f$ is a computable vector in $L^p[?\pi,\pi]$ and $t_0 \in [-\pi,\pi]$ is Schnorr random, then the Fourier series for $f$ converges at $t_0$.
(2) If $t_0 \in [-\pi,\pi]$ is not Schnorr random, then there is a computable function $f : [-\pi,\pi] \rightarrow \mathbb{C}$ whose Fourier series diverges at $t_0$.
This is joint work with Timothy H. McNicholl, and Jason Rute.
Carleson's Theorem states that for $1 < p < \infty$, the Fourier series of a function $f$ in $L^p[-\pi,\pi]$ converges to $f$ almost everywhere. We consider this theorem in the context of computable analysis and show the following two results.
(1) For a computable $p > 1$, if $f$ is a computable vector in $L^p[?\pi,\pi]$ and $t_0 \in [-\pi,\pi]$ is Schnorr random, then the Fourier series for $f$ converges at $t_0$.
(2) If $t_0 \in [-\pi,\pi]$ i...

03D32 ; 42A20 ; 03D78 ; 68Q30

... Lire [+]

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

Research talks;Computer Science;Logic and Foundations

I will discuss two recent interactions of the field called randomness via algorithmic tests. With Yokoyama and Triplett, I study the reverse mathematical strength of two results of analysis. (1) The Jordan decomposition theorem says that every function of bounded variation is the difference of two nondecreasing functions. This is equivalent to ACA or to WKL, depending on the formalisation. (2) A theorem of Lebesgue states that each function of bounded variation is differentiable almost everywhere. This turns out to be equivalent WWKL (with some fine work left to be done on the amount of induction needed). The Gamma operator maps Turing degrees to real numbers; a smaller value means a higher complexity. This operator has an analog in the field of cardinal characteristics along the lines of the Rupprecht correspondence [4]; also see [1]. Given a real p between 0 and 1/2, d(p) is the least size of a set G so that for each set x of natural numbers, there is a set y in G such that x and y agree on asymptotically more than p of the bits. Clearly, d is monotonic. Based on Monin's recent solution to the Gamma question (see [3] for background, and the post in [2] for a sketch), I will discuss the result with J. Brendle that the cardinal d(p) doesn't depend on p. Remaining open questions in computability (is weakly Schnorr engulfing equivalent to "Gamma = 0"?) nicely match open questions about these cardinal characteristics. I will discuss two recent interactions of the field called randomness via algorithmic tests. With Yokoyama and Triplett, I study the reverse mathematical strength of two results of analysis. (1) The Jordan decomposition theorem says that every function of bounded variation is the difference of two nondecreasing functions. This is equivalent to ACA or to WKL, depending on the formalisation. (2) A theorem of Lebesgue states that each function of ...

03D25 ; 03D32 ; 03F60 ; 68Q30

... 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.

- xviii; 511 p.
ISBN 978-1-4704-3182-2

Mathematical surveys and monographs , 0220

Localisation : Collection 1er étage

théorie de l'information # complexité de Kolmogorov # complexité de calcul # calcul algorithmique

68Q30 ; 03D32 ; 60A99 ; 03-02 ; 03D15

... Lire [+]

Z