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: |
| Sumario: | 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. |
|---|