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

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Becher, Verónica Andrea, Figueira, Santiago Daniel
Publicado: 2006
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00224812_v71_n4_p1411_Becher
http://hdl.handle.net/20.500.12110/paper_00224812_v71_n4_p1411_Becher
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_00224812_v71_n4_p1411_Becher
record_format dspace
spelling paper:paper_00224812_v71_n4_p1411_Becher2023-06-08T14:51:09Z Randomness and halting probabilities Becher, Verónica Andrea Figueira, Santiago Daniel 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. 2006 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00224812_v71_n4_p1411_Becher 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.
author Becher, Verónica Andrea
Figueira, Santiago Daniel
spellingShingle Becher, Verónica Andrea
Figueira, Santiago Daniel
Randomness and halting probabilities
author_facet Becher, Verónica Andrea
Figueira, Santiago Daniel
author_sort Becher, Verónica Andrea
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
publishDate 2006
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00224812_v71_n4_p1411_Becher
http://hdl.handle.net/20.500.12110/paper_00224812_v71_n4_p1411_Becher
work_keys_str_mv AT becherveronicaandrea randomnessandhaltingprobabilities
AT figueirasantiagodaniel randomnessandhaltingprobabilities
_version_ 1768542161942347776

Ejemplares similares