Randomness and universal machines
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...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Artículo publishedVersion |
| Publicado: |
2006
|
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_0885064X_v22_n6_p738_Figueira http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0885064X_v22_n6_p738_Figueira_oai |
| Aporte de: |
| id |
I28-R145-paper_0885064X_v22_n6_p738_Figueira_oai |
|---|---|
| record_format |
dspace |
| spelling |
I28-R145-paper_0885064X_v22_n6_p738_Figueira_oai2020-10-19 Figueira, S. Stephan, F. Wu, G. 2006 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. Fil:Figueira, S. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf http://hdl.handle.net/20.500.12110/paper_0885064X_v22_n6_p738_Figueira info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar J. Complexity 2006;22(6):738-751 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 Randomness and universal machines info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0885064X_v22_n6_p738_Figueira_oai |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-145 |
| collection |
Repositorio Digital de la Universidad de Buenos Aires (UBA) |
| topic |
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 |
| spellingShingle |
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 Figueira, S. Stephan, F. Wu, G. Randomness and universal machines |
| topic_facet |
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 |
| description |
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. |
| format |
Artículo Artículo publishedVersion |
| author |
Figueira, S. Stephan, F. Wu, G. |
| author_facet |
Figueira, S. Stephan, F. Wu, G. |
| author_sort |
Figueira, S. |
| title |
Randomness and universal machines |
| title_short |
Randomness and universal machines |
| title_full |
Randomness and universal machines |
| title_fullStr |
Randomness and universal machines |
| title_full_unstemmed |
Randomness and universal machines |
| title_sort |
randomness and universal machines |
| publishDate |
2006 |
| url |
http://hdl.handle.net/20.500.12110/paper_0885064X_v22_n6_p738_Figueira http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0885064X_v22_n6_p738_Figueira_oai |
| work_keys_str_mv |
AT figueiras randomnessanduniversalmachines AT stephanf randomnessanduniversalmachines AT wug randomnessanduniversalmachines |
| _version_ |
1766026713810075648 |