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...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_00294527_v46_n1_p51_Becher |
| Aporte de: |
| id |
todo:paper_00294527_v46_n1_p51_Becher |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_00294527_v46_n1_p51_Becher2023-10-03T14:39:13Z Program size complexity for possibly infinite computations Becher, V. Figueira, S. Nies, A. Picchi, S. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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 Becher, V. Figueira, S. Nies, A. Picchi, S. 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. |
| format |
JOUR |
| author |
Becher, V. Figueira, S. Nies, A. Picchi, S. |
| author_facet |
Becher, V. Figueira, S. Nies, A. Picchi, S. |
| author_sort |
Becher, V. |
| 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 |
| url |
http://hdl.handle.net/20.500.12110/paper_00294527_v46_n1_p51_Becher |
| work_keys_str_mv |
AT becherv programsizecomplexityforpossiblyinfinitecomputations AT figueiras programsizecomplexityforpossiblyinfinitecomputations AT niesa programsizecomplexityforpossiblyinfinitecomputations AT picchis programsizecomplexityforpossiblyinfinitecomputations |
| _version_ |
1807319852191318016 |