Randomness and halting probabilities
We consider the question of randomness of the probability ΩU[X] that an optimal Turing machine U halts and outputs a string in a fixed set X. The main results are as follows: ΩU[X] is random whenever X is Σn0-complete or Πn0-complete for some n ≥ 2. However, for n ≥ 2, ΩU[X] is not n-random when X i...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | JOUR |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_00224812_v71_n4_p1411_Becher |
| Aporte de: |
| id |
todo:paper_00224812_v71_n4_p1411_Becher |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_00224812_v71_n4_p1411_Becher2023-10-03T14:33:16Z Randomness and halting probabilities Becher, V. Figueira, S. Grigorieff, S. Miller, J.S. We consider the question of randomness of the probability ΩU[X] that an optimal Turing machine U halts and outputs a string in a fixed set X. The main results are as follows: ΩU[X] is random whenever X is Σn0-complete or Πn0-complete for some n ≥ 2. However, for n ≥ 2, ΩU[X] is not n-random when X is Σn0 or Πn0. Nevertheless, there exists Δn+10 sets such that ΩU[X] is n-random. There are Δ20 sets X such that ΩU[X] is rational. Also, for every n ≥ 1, there exists a set X which is Δn+10 and Σn 0-hard such that ΩU[X] is not random. We also look at the range of ΩU as an operator. We prove that the set {ΩU[X]: X ⊆ 2<ω} is a finite union of closed intervals. It follows that for any optimal machine U and any sufficiently small real r, there is a set X ⊆ 2<ω recursive in ∅′ ⊕ r, such that ΩU[X] = r. The same questions are also considered in the context of infinite computations, and lead to similar results. © 2006, Association for Symbolic Logic. Fil:Becher, V. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 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_00224812_v71_n4_p1411_Becher |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| description |
We consider the question of randomness of the probability ΩU[X] that an optimal Turing machine U halts and outputs a string in a fixed set X. The main results are as follows: ΩU[X] is random whenever X is Σn0-complete or Πn0-complete for some n ≥ 2. However, for n ≥ 2, ΩU[X] is not n-random when X is Σn0 or Πn0. Nevertheless, there exists Δn+10 sets such that ΩU[X] is n-random. There are Δ20 sets X such that ΩU[X] is rational. Also, for every n ≥ 1, there exists a set X which is Δn+10 and Σn 0-hard such that ΩU[X] is not random. We also look at the range of ΩU as an operator. We prove that the set {ΩU[X]: X ⊆ 2<ω} is a finite union of closed intervals. It follows that for any optimal machine U and any sufficiently small real r, there is a set X ⊆ 2<ω recursive in ∅′ ⊕ r, such that ΩU[X] = r. The same questions are also considered in the context of infinite computations, and lead to similar results. © 2006, Association for Symbolic Logic. |
| format |
JOUR |
| author |
Becher, V. Figueira, S. Grigorieff, S. Miller, J.S. |
| spellingShingle |
Becher, V. Figueira, S. Grigorieff, S. Miller, J.S. Randomness and halting probabilities |
| author_facet |
Becher, V. Figueira, S. Grigorieff, S. Miller, J.S. |
| author_sort |
Becher, V. |
| title |
Randomness and halting probabilities |
| title_short |
Randomness and halting probabilities |
| title_full |
Randomness and halting probabilities |
| title_fullStr |
Randomness and halting probabilities |
| title_full_unstemmed |
Randomness and halting probabilities |
| title_sort |
randomness and halting probabilities |
| url |
http://hdl.handle.net/20.500.12110/paper_00224812_v71_n4_p1411_Becher |
| work_keys_str_mv |
AT becherv randomnessandhaltingprobabilities AT figueiras randomnessandhaltingprobabilities AT grigorieffs randomnessandhaltingprobabilities AT millerjs randomnessandhaltingprobabilities |
| _version_ |
1807320117940322304 |