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

Ejemplares similares

Ejemplares similares