Program size complexity for possibly infinite computations

We define a program size complexity function H∞ as a variant of the prefix-free Kolmogorov complexity, based on Turing monotone machines performing possibly unending computations. We consider definitions of randomness and triviality for sequences in {0, 1}ω relative to the H∞ complexity. We prove th...

Descripción completa

Guardado en:
Detalles Bibliográficos
Publicado: 2005
Materias:
Infinite computations
KOLMOGOROV complexity
Program size complexity
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00294527_v46_n1_p51_Becher
http://hdl.handle.net/20.500.12110/paper_00294527_v46_n1_p51_Becher
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_00294527_v46_n1_p51_Becher
record_format dspace
spelling paper:paper_00294527_v46_n1_p51_Becher2025-07-30T17:36:56Z Program size complexity for possibly infinite computations Infinite computations KOLMOGOROV complexity Program size complexity We define a program size complexity function H∞ as a variant of the prefix-free Kolmogorov complexity, based on Turing monotone machines performing possibly unending computations. We consider definitions of randomness and triviality for sequences in {0, 1}ω relative to the H∞ complexity. We prove that the classes of Martin-Löf random sequences and H∞-random sequences coincide and that the H∞-trivial sequences are exactly the recursive ones. We also study some properties of H∞ and compare it with other complexity functions. In particular, H∞ is different from H A, the prefix-free complexity of monotone machines with oracle A. © 2005 University of Notre Dame. 2005 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00294527_v46_n1_p51_Becher http://hdl.handle.net/20.500.12110/paper_00294527_v46_n1_p51_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
KOLMOGOROV complexity
Program size complexity
spellingShingle Infinite computations
KOLMOGOROV complexity
Program size complexity
Program size complexity for possibly infinite computations
topic_facet Infinite computations
KOLMOGOROV complexity
Program size complexity
description We define a program size complexity function H∞ as a variant of the prefix-free Kolmogorov complexity, based on Turing monotone machines performing possibly unending computations. We consider definitions of randomness and triviality for sequences in {0, 1}ω relative to the H∞ complexity. We prove that the classes of Martin-Löf random sequences and H∞-random sequences coincide and that the H∞-trivial sequences are exactly the recursive ones. We also study some properties of H∞ and compare it with other complexity functions. In particular, H∞ is different from H A, the prefix-free complexity of monotone machines with oracle A. © 2005 University of Notre Dame.
title Program size complexity for possibly infinite computations
title_short Program size complexity for possibly infinite computations
title_full Program size complexity for possibly infinite computations
title_fullStr Program size complexity for possibly infinite computations
title_full_unstemmed Program size complexity for possibly infinite computations
title_sort program size complexity for possibly infinite computations
publishDate 2005
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00294527_v46_n1_p51_Becher
http://hdl.handle.net/20.500.12110/paper_00294527_v46_n1_p51_Becher
_version_ 1840327486226825216

Ejemplares similares