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 https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0885064X_v22_n6_p738_Figueira_oai |
| Aporte de: |
| Sumario: | 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. |
|---|