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, V., Figueira, S., Grigorieff, S., Miller, J.S.
Formato: JOUR
Acceso en línea: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