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
id todo:paper_01692968_v51_n4_p325_Becher
record_format dspace
spelling todo:paper_01692968_v51_n4_p325_Becher2023-10-03T15:07:02Z Another example of higher order randomness Becher, V. Chaitin, G. Infinite computations Program size complexity Randomness Algorithms Computational complexity Computer program listings Computer simulation Probability Problem solving Finite size complexity Random processes 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_01692968_v51_n4_p325_Becher
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Infinite computations
Program size complexity
Randomness
Algorithms
Computational complexity
Computer program listings
Computer simulation
Probability
Problem solving
Finite size complexity
Random processes
spellingShingle Infinite computations
Program size complexity
Randomness
Algorithms
Computational complexity
Computer program listings
Computer simulation
Probability
Problem solving
Finite size complexity
Random processes
Becher, V.
Chaitin, G.
Another example of higher order randomness
topic_facet Infinite computations
Program size complexity
Randomness
Algorithms
Computational complexity
Computer program listings
Computer simulation
Probability
Problem solving
Finite size complexity
Random processes
description 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.
format JOUR
author Becher, V.
Chaitin, G.
author_facet Becher, V.
Chaitin, G.
author_sort Becher, V.
title Another example of higher order randomness
title_short Another example of higher order randomness
title_full Another example of higher order randomness
title_fullStr Another example of higher order randomness
title_full_unstemmed Another example of higher order randomness
title_sort another example of higher order randomness
url http://hdl.handle.net/20.500.12110/paper_01692968_v51_n4_p325_Becher
work_keys_str_mv AT becherv anotherexampleofhigherorderrandomness
AT chaiting anotherexampleofhigherorderrandomness
_version_ 1807324006374703104

Ejemplares similares