Another example of higher order randomness

We consider the notion of algorithmic randomness relative to an oracle. We prove that the probability β that a program for infinite computations (a program that never halts) outputs a cofinite set is random in the second jump of the halting problem. Indeed, we prove that β is exactly as random as th...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Becher, V., Chaitin, G.
Formato: JOUR
Materias:
Infinite computations
Program size complexity
Randomness
Algorithms
Computational complexity
Computer program listings
Computer simulation
Probability
Problem solving
Finite size complexity
Random processes
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_01692968_v51_n4_p325_Becher
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
Descripción
Sumario:We consider the notion of algorithmic randomness relative to an oracle. We prove that the probability β that a program for infinite computations (a program that never halts) outputs a cofinite set is random in the second jump of the halting problem. Indeed, we prove that β is exactly as random as the halting probability of a universal machine equipped with an oracle for the second jump of the halting problem, in spite of the fact that β is defined without considering oracles.

Ejemplares similares