Artículo
Abstract:
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.
Registro:
| Documento: | Artículo |
| Título: | Indifferent sets |
| Autor: | Figueira, S.; Miller, J.S.; Nies, A. |
| Filiación: | Departamento de Computacin, FCEyN, Pabelln I (C1428EGA), Buenos Aires, Argentina CONICET, Argentina Department of Mathematics, University of Wisconsin, Madison, WI 53706-1388, United States Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand |
| Palabras clave: | 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 |
| Año: | 2009 |
| Volumen: | 19 |
| Número: | 2 |
| Página de inicio: | 425 |
| Página de fin: | 443 |
| DOI: | http://dx.doi.org/10.1093/logcom/exn101 |
| Título revista: | Journal of Logic and Computation |
| Título revista abreviado: | J Logic Comput |
| ISSN: | 0955792X |
| CODEN: | JLCOE |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0955792X_v19_n2_p425_Figueira |
Referencias:
- Ambos-Spies, K., Mayordomo, E., Resource bounded measure and randomness (1997) Complexity Logic and Recursion Theory, pp. 1-47. , A. Sorbi, ed, pp, Marcel Dekker, New York NY
- Ambos-Spies, K., Terwijn, S., Zheng, X., Resource bounded randomness and weakly complete problems (1997) Theoretical Computer Science, 172, pp. 195-207
- Becher, V., Figueira, S., An example of a computable absolutely normal number (2002) Theoretical Computer Science, 270, pp. 947-958
- Becher, V., Figueira, S., Picchi, R., Turing's unpublished algorithm for normal numbers (2007) Theoretical Computer Science, 70, pp. 126-138
- Gács, P., Every set is reducible to a random one (1986) Information and Control, 70, pp. 186-192
- Jockusch Jr, C., Soare, R.I., Π0 1 classes and degrees of theories (1972) Transactions of the American Mathematical Society, 173, pp. 33-56
- A. Kučera. Measure, Π0 1 classes, and complete extensions of PA. Lecture Notes in Mathematics, 1141, 245-259, 1985; Ladner, R.E., Mitotic recursively enumerable sets (1973) The Journal of Symbolic Logic, 38, pp. 199-211
- Lutz, J.H., Category and measure in complexity classes (1990) SIAM Journal of Computing, 19, pp. 1100-1131
- Martin-Löf, P., The definition of random sequences (1966) Information and Control, 9, pp. 602-619
- Miller, J.S., Yu, L., On initial segment complexity and degrees of randomness (2008) Transactions of the American Mathematical Society, 360, pp. 3193-3210
- Oxtoby, J.C., (1980) Measure and Category, , 2nd edn. Springer, New York
- Schnorr, C.-P., Zufälligkeit und Wahrscheinlichkeit (1971) Lecture Notes in Mathematics, 218. , of, Springer, Heidelberg
- Soare, R.I., (1987) Recursively Enumerable Sets and Degrees, , Springer, Heidelberg
- Soare, R.I., Computability and recursion (1996) Bulletin of Symbolic Logic, 2, pp. 284-321
- Soare, R.I., Computability and incomputability (2007) Lecture Notes in Computer Science, 4497, pp. 705-715. , Computation and Logic in the Real World. of, S. B. Cooper, B. Lowe and A. Sorbi, eds, pp, Springer, Berlin/Heidelberg
- Trahtenbrot, B.A., On autoreducibility (1970) Doklady Akademii Nauk SSSR, 192, pp. 1224-1227
- van Lambalgen, M., (1987) Random Sequences, , http://staff.science.uva.nl/∼michiell/docs/fFDiss.pdf, PhD thesis, University of Amserdam, Avaialble at
- van Lambalgen, M., The axiomatization of randomness (1990) Journal of Symbolic Logic, 55, pp. 1143-1167
Citas:
---------- APA ----------
Figueira, S., Miller, J.S. & Nies, A. (2009) . Indifferent sets. Journal of Logic and Computation, 19(2), 425-443.http://dx.doi.org/10.1093/logcom/exn101
---------- CHICAGO ----------
Figueira, S., Miller, J.S., Nies, A. "Indifferent sets" . Journal of Logic and Computation 19, no. 2 (2009) : 425-443.http://dx.doi.org/10.1093/logcom/exn101
---------- MLA ----------
Figueira, S., Miller, J.S., Nies, A. "Indifferent sets" . Journal of Logic and Computation, vol. 19, no. 2, 2009, pp. 425-443.http://dx.doi.org/10.1093/logcom/exn101
---------- VANCOUVER ----------
Figueira, S., Miller, J.S., Nies, A. Indifferent sets. J Logic Comput. 2009;19(2):425-443.http://dx.doi.org/10.1093/logcom/exn101
