Another Example of Higher Order Randomness

• Autorzy: Becher V. , Chaitin G.
• Języki publikacji: EN

Abstrakty

EN

We consider the notion of algorithmic randomness relative to an oracle. We prove that the probability b 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 b 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 b is defined without considering oracles.

Słowa kluczowe

EN

randomness; program size complexity; infinite computations

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2002
• Tom: Vol. 51, nr 4
• Strony: 325--338
• Opis fizyczny: bibliogr. 15 poz.

Twórcy

autor

Becher V.

autor

Chaitin G.

• Departamento de Computacion, Facultad de Ciencias Exactas y Naturales, Universidad de Buones Aires, Pabellón 1 - Ciudad Universitaria (1428) Buenoa Aires, Argentina [e-mail],