Continuous Randomness via Transformations of 2-Random Sequences
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913256641134592 |
|---|---|
| author | Porter, Christopher P. |
| author_facet | Porter, Christopher P. |
| contents | Reimann and Slaman initiated the study of sequences that are Martin-Löf random with respect to a continuous measure, establishing fundamental facts about NCR, the collection of sequences that are not Martin-Löf random with respect to any continuous measure. In the case of sequences that are random with respect to a computable, continuous measure, the picture is fairly well-understood: such sequences are truth-table equivalent to a Martin-Löf random sequence. However, given a sequence that is random with respect to a continuous measure but not with respect to any computable measure, we can ask: how close to effective is the measure with respect to which it is continuously random?
In this study, we take up this question by examining various transformations of 2-random sequences (sequences that are Martin-Löf random relative to the halting set $\emptyset'$) to establish several results on sequences that are continuously random with respect to a measure that is computable in $\emptyset'$. In particular, we show that (i) every noncomputable sequence that is computable from a 2-random sequence is Martin-Löf random with respect to a continuous, $\emptyset'$-computable measure and (ii) the Turing jump of every 2-random sequence is Martin-Löf random with respect to a continuous, $\emptyset'$-computable measure. From these results, we obtain examples of sequences that are not proper, i.e., not random with respect to any computable measure, but are random with respect to a continuous, $\emptyset'$-computable measure. Lastly, we consider the behavior of 2-randomness under a wider class of effective operators (c.e. operators, pseudojump operators, and operators defined in terms of pseudojump inversion), showing that these too yield sequences that are Martin-Löf random with respect to a continuous, $\emptyset'$-computable measure. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_04047 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Continuous Randomness via Transformations of 2-Random Sequences Porter, Christopher P. Logic Reimann and Slaman initiated the study of sequences that are Martin-Löf random with respect to a continuous measure, establishing fundamental facts about NCR, the collection of sequences that are not Martin-Löf random with respect to any continuous measure. In the case of sequences that are random with respect to a computable, continuous measure, the picture is fairly well-understood: such sequences are truth-table equivalent to a Martin-Löf random sequence. However, given a sequence that is random with respect to a continuous measure but not with respect to any computable measure, we can ask: how close to effective is the measure with respect to which it is continuously random? In this study, we take up this question by examining various transformations of 2-random sequences (sequences that are Martin-Löf random relative to the halting set $\emptyset'$) to establish several results on sequences that are continuously random with respect to a measure that is computable in $\emptyset'$. In particular, we show that (i) every noncomputable sequence that is computable from a 2-random sequence is Martin-Löf random with respect to a continuous, $\emptyset'$-computable measure and (ii) the Turing jump of every 2-random sequence is Martin-Löf random with respect to a continuous, $\emptyset'$-computable measure. From these results, we obtain examples of sequences that are not proper, i.e., not random with respect to any computable measure, but are random with respect to a continuous, $\emptyset'$-computable measure. Lastly, we consider the behavior of 2-randomness under a wider class of effective operators (c.e. operators, pseudojump operators, and operators defined in terms of pseudojump inversion), showing that these too yield sequences that are Martin-Löf random with respect to a continuous, $\emptyset'$-computable measure. |
| title | Continuous Randomness via Transformations of 2-Random Sequences |
| topic | Logic |
| url | https://arxiv.org/abs/2403.04047 |