Random reals à la Chaitin with or without prefix-freeness

Mostrar todas las versiones(3)

We give a general theorem that provides examples of n-random reals à la Chaitin, for every n ≥ 1; these are halting probabilities of partial computable functions that are universal by adjunction for the class of all partial computable functions, The same result holds for the class functions of parti...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Becher, V., Grigorieff, S.
Formato: Artículo publishedVersion
Publicado: 2007
Materias:
Algorithmic randomness
Kolmogorov complexity
Omega numbers
Random reals
Function evaluation
Probability
Problem solving
Theorem proving
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03043975_v385_n1-3_p193_Becher
http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_03043975_v385_n1-3_p193_Becher_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-paper_03043975_v385_n1-3_p193_Becher_oai
record_format dspace
spelling I28-R145-paper_03043975_v385_n1-3_p193_Becher_oai2020-10-19 Becher, V. Grigorieff, S. 2007 We give a general theorem that provides examples of n-random reals à la Chaitin, for every n ≥ 1; these are halting probabilities of partial computable functions that are universal by adjunction for the class of all partial computable functions, The same result holds for the class functions of partial computable functions with prefix-free domain. Thus, the usual technical requirement of prefix-freeness on domains is an option which we show to be non-critical when dealing with universality by adjunction. We also prove that the condition of universality by adjunction (which, though particular, is a very natural case of optimality) is essential in our theorem. © 2007 Elsevier Ltd. All rights reserved. Fil:Becher, V. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf http://hdl.handle.net/20.500.12110/paper_03043975_v385_n1-3_p193_Becher info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Theor Comput Sci 2007;385(1-3):193-201 Algorithmic randomness Kolmogorov complexity Omega numbers Random reals Function evaluation Probability Problem solving Algorithmic randomness Kolmogorov complexity Omega numbers Random reals Theorem proving Random reals à la Chaitin with or without prefix-freeness info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_03043975_v385_n1-3_p193_Becher_oai
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (UBA)
topic Algorithmic randomness
Kolmogorov complexity
Omega numbers
Random reals
Function evaluation
Probability
Problem solving
Algorithmic randomness
Kolmogorov complexity
Omega numbers
Random reals
Theorem proving
spellingShingle Algorithmic randomness
Kolmogorov complexity
Omega numbers
Random reals
Function evaluation
Probability
Problem solving
Algorithmic randomness
Kolmogorov complexity
Omega numbers
Random reals
Theorem proving
Becher, V.
Grigorieff, S.
Random reals à la Chaitin with or without prefix-freeness
topic_facet Algorithmic randomness
Kolmogorov complexity
Omega numbers
Random reals
Function evaluation
Probability
Problem solving
Algorithmic randomness
Kolmogorov complexity
Omega numbers
Random reals
Theorem proving
description We give a general theorem that provides examples of n-random reals à la Chaitin, for every n ≥ 1; these are halting probabilities of partial computable functions that are universal by adjunction for the class of all partial computable functions, The same result holds for the class functions of partial computable functions with prefix-free domain. Thus, the usual technical requirement of prefix-freeness on domains is an option which we show to be non-critical when dealing with universality by adjunction. We also prove that the condition of universality by adjunction (which, though particular, is a very natural case of optimality) is essential in our theorem. © 2007 Elsevier Ltd. All rights reserved.
format Artículo
Artículo
publishedVersion
author Becher, V.
Grigorieff, S.
author_facet Becher, V.
Grigorieff, S.
author_sort Becher, V.
title Random reals à la Chaitin with or without prefix-freeness
title_short Random reals à la Chaitin with or without prefix-freeness
title_full Random reals à la Chaitin with or without prefix-freeness
title_fullStr Random reals à la Chaitin with or without prefix-freeness
title_full_unstemmed Random reals à la Chaitin with or without prefix-freeness
title_sort random reals à la chaitin with or without prefix-freeness
publishDate 2007
url http://hdl.handle.net/20.500.12110/paper_03043975_v385_n1-3_p193_Becher
http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_03043975_v385_n1-3_p193_Becher_oai
work_keys_str_mv AT becherv randomrealsalachaitinwithorwithoutprefixfreeness
AT grigorieffs randomrealsalachaitinwithorwithoutprefixfreeness
_version_ 1766026689926660096

Ejemplares similares