Indifferent sets
We define the notion of indifferent set with respect to a given class of 0,1-sequences. Roughly, for a set A in the class, a set of natural numbers I is indifferent for A with respect to the class if it does not matter how we change A at the positions in I: the new sequence continues to be in the gi...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_0955792X_v19_n2_p425_Figueira |
| Aporte de: |
| id |
todo:paper_0955792X_v19_n2_p425_Figueira |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_0955792X_v19_n2_p425_Figueira2023-10-03T15:51:49Z Indifferent sets Figueira, S. Miller, J.S. Nies, A. Absolutely normal number Autoreducibility Hyperimmune set Indifferent set Randomness Sparseness Turing degree Absolutely normal number Autoreducibility Hyperimmune set Indifferent set Randomness Sparseness Turing degree Number theory We define the notion of indifferent set with respect to a given class of 0,1-sequences. Roughly, for a set A in the class, a set of natural numbers I is indifferent for A with respect to the class if it does not matter how we change A at the positions in I: the new sequence continues to be in the given class. We are especially interested in studying those sets that are indifferent with respect to classes containing different types of stochastic sequences. For the class of Martin-Lf random sequences, we show that every random sequence has an infinite indifferent set and that there is no universal indifferent set. We show that indifferent sets must be sparse, in fact sparse enough to decide the halting problem. We prove the existence of co-c.e. indifferent sets, including a co-c.e. set that is indifferent for every 2-random sequence with respect to the class of random sequences. For the class of absolutely normal numbers, we show that there are computable indifferent sets with respect to that class and we conclude that there is an absolutely normal real number in every non-trivial many-one degree. Fil:Figueira, S. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0955792X_v19_n2_p425_Figueira |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Absolutely normal number Autoreducibility Hyperimmune set Indifferent set Randomness Sparseness Turing degree Absolutely normal number Autoreducibility Hyperimmune set Indifferent set Randomness Sparseness Turing degree Number theory |
| spellingShingle |
Absolutely normal number Autoreducibility Hyperimmune set Indifferent set Randomness Sparseness Turing degree Absolutely normal number Autoreducibility Hyperimmune set Indifferent set Randomness Sparseness Turing degree Number theory Figueira, S. Miller, J.S. Nies, A. Indifferent sets |
| topic_facet |
Absolutely normal number Autoreducibility Hyperimmune set Indifferent set Randomness Sparseness Turing degree Absolutely normal number Autoreducibility Hyperimmune set Indifferent set Randomness Sparseness Turing degree Number theory |
| description |
We define the notion of indifferent set with respect to a given class of 0,1-sequences. Roughly, for a set A in the class, a set of natural numbers I is indifferent for A with respect to the class if it does not matter how we change A at the positions in I: the new sequence continues to be in the given class. We are especially interested in studying those sets that are indifferent with respect to classes containing different types of stochastic sequences. For the class of Martin-Lf random sequences, we show that every random sequence has an infinite indifferent set and that there is no universal indifferent set. We show that indifferent sets must be sparse, in fact sparse enough to decide the halting problem. We prove the existence of co-c.e. indifferent sets, including a co-c.e. set that is indifferent for every 2-random sequence with respect to the class of random sequences. For the class of absolutely normal numbers, we show that there are computable indifferent sets with respect to that class and we conclude that there is an absolutely normal real number in every non-trivial many-one degree. |
| format |
JOUR |
| author |
Figueira, S. Miller, J.S. Nies, A. |
| author_facet |
Figueira, S. Miller, J.S. Nies, A. |
| author_sort |
Figueira, S. |
| title |
Indifferent sets |
| title_short |
Indifferent sets |
| title_full |
Indifferent sets |
| title_fullStr |
Indifferent sets |
| title_full_unstemmed |
Indifferent sets |
| title_sort |
indifferent sets |
| url |
http://hdl.handle.net/20.500.12110/paper_0955792X_v19_n2_p425_Figueira |
| work_keys_str_mv |
AT figueiras indifferentsets AT millerjs indifferentsets AT niesa indifferentsets |
| _version_ |
1807314726293602304 |