Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

The present work investigates several questions from a recent survey of Miller and Nies related to Chaitin's Ω numbers and their dependence on the underlying universal machine. Furthermore, the notion ΩU [X] = ∑p : U (p) ↓ ∈ X 2- | p | is studied for various sets X and universal machines U. A universal machine U is constructed such that for all x, ΩU [{ x }] = 21 - H (x). For such a universal machine there exists a co-r.e. set X such that ΩU [X] is neither left-r.e. nor Martin-Löf random. Furthermore, one of the open problems of Miller and Nies is answered completely by showing that there is a sequence Un of universal machines such that the truth-table degrees of the ΩUn form an antichain. Finally, it is shown that the members of hyperimmune-free Turing degree of a given Π1 0-class are not low for Ω unless this class contains a recursive set. © 2006 Elsevier Inc. All rights reserved.

Registro:

Documento: Artículo
Título:Randomness and universal machines
Autor:Figueira, S.; Stephan, F.; Wu, G.
Filiación:Department of Computer Science, FCEyN, University of Buenos Aires, Argentina
Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore, 117543, Singapore
School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, 637616, Singapore
Palabras clave:Algorithmic randomness; Halting probability; Kolmogorov complexity; Recursion theory; Truth-table degrees; Universal machines; Ω-numbers; Algorithms; Turing machines; Algorithmic randomness; Halting probability; Kolmogorov complexity; Recursion theory; Truth-table degrees; Universal machines; Ω-numbers; Random number generation
Año:2006
Volumen:22
Número:6
Página de inicio:738
Página de fin:751
DOI: http://dx.doi.org/10.1016/j.jco.2006.05.001
Título revista:Journal of Complexity
Título revista abreviado:J. Complexity
ISSN:0885064X
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0885064X_v22_n6_p738_Figueira.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v22_n6_p738_Figueira

Referencias:

  • Becher, V., Figueira, S., Nies, A., Picchi, S., Program size complexity for possibly infinite computations (2005) Notre Dame J. Formal Logic, 46 (1), pp. 51-64
  • Becher, V., Grigorieff, S., Random reals and possibly infinite computations, Part I: randomness in ∅′ (2005) J. Symbolic Logic, 70 (3), pp. 891-913
  • Bennett, C.H., Logical depth and physical complexity (1988) The Universal Turing Machine, a Half-Century Survey, pp. 227-258. , Herken R. (Ed), Oxford University Press, Oxford
  • Calude, C.S., Nies, A., Chaitin Ω numbers and strong reducibilities, Proceedings of the First Japan-New Zealand Workshop on Logic in Computer Science (Auckland, 1997) (1997) J. Universal Comput. Sci., 3 (11), pp. 1162-1166
  • Calude, C.S., Hertling, P., Khoussainov, B., Wang, Y., Recursively enumerable reals and Chaitin's Ω number (2001) Theoret. Comput. Sci., 255 (1-2), pp. 125-149. , See also: STACS 1998 (Paris, 1998), Springer Lecture Notes in Computer Science, vol. 1373, Springer, Berlin, 1998, pp. 596-606
  • Chaitin, G., A theory of program size formally identical to information theory (1975) J. Assoc. Comput. Machinery, 22, pp. 329-340
  • Cutland, N., (1980) Computability, an Introduction to Recursive Function Theory, , Cambridge University Press, Cambridge
  • Downey, R.G., Hirschfeldt, D., Miller, J.S., Nies, A., Relativizing Chaitin's halting probability (2005) J. Math. Logic, 5, pp. 167-192
  • Jockusch Jr., C., The degrees of bi-immune sets (1969) Z. Math. Logik Grundl. Math., 15, pp. 135-140
  • Jockusch Jr., C., Soare, R., Π1 0 classes and degrees of theories (1972) Trans. Amer. Math. Soc., 173, pp. 33-56
  • Kučera, A., Slaman, T.A., Randomness and recursive enumerability (2001) SIAM J. Comput., 31 (1), pp. 199-211
  • Li, M., Vitányi, P., (1997) An Introduction to Kolmogorov Complexity and its Applications. second ed., , Springer, Heidelberg
  • Martin-Löf, P., The definition of random sequences (1966) Inform. and Control, 9, pp. 602-619
  • Miller, W., Martin, D.A., The degrees of hyperimmune sets (1968) Z. Math. Logik Grundl. Math., 14, pp. 159-166
  • Nies, A., Lowness properties and randomness (2005) Adv. in Math., 197, pp. 274-305
  • Nies, S.A., Terwijn, F., Stephan. Randomness relativization and Turing degrees (2005) J. Symbolic Logic, 70 (2), pp. 515-535
  • Schnorr, C.P., (1971) Zufälligkeit und Wahrscheinlichkeit, Springer Lecture Notes in Mathematics, 218. , Springer, Berlin
  • Soare, R., (1987) Recursively Enumerable Sets and Degrees, , Springer, Heidelberg
  • Weihrauch, K., (1987) Computability, EATCS Monographs on Theoretical Computer Science, 9. , Springer, Heidelberg

Citas:

---------- APA ----------
Figueira, S., Stephan, F. & Wu, G. (2006) . Randomness and universal machines. Journal of Complexity, 22(6), 738-751.
http://dx.doi.org/10.1016/j.jco.2006.05.001
---------- CHICAGO ----------
Figueira, S., Stephan, F., Wu, G. "Randomness and universal machines" . Journal of Complexity 22, no. 6 (2006) : 738-751.
http://dx.doi.org/10.1016/j.jco.2006.05.001
---------- MLA ----------
Figueira, S., Stephan, F., Wu, G. "Randomness and universal machines" . Journal of Complexity, vol. 22, no. 6, 2006, pp. 738-751.
http://dx.doi.org/10.1016/j.jco.2006.05.001
---------- VANCOUVER ----------
Figueira, S., Stephan, F., Wu, G. Randomness and universal machines. J. Complexity. 2006;22(6):738-751.
http://dx.doi.org/10.1016/j.jco.2006.05.001