There is a deep 1-generic set
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914932011827200 |
|---|---|
| author | Li, Ang |
| author_facet | Li, Ang |
| contents | An infinite binary sequence is Bennett deep if, for any computable time bound, the difference between the time-bounded prefix-free Kolmogorov complexity and the prefix-free Kolmogorov complexity of its initial segments is eventually unbounded. It is known that weakly 2-generic sets are shallow, i.e. not deep. In this paper, we show that there is a deep 1-generic set. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_00631 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | There is a deep 1-generic set Li, Ang Logic Logic in Computer Science 03D30, 68Q30 An infinite binary sequence is Bennett deep if, for any computable time bound, the difference between the time-bounded prefix-free Kolmogorov complexity and the prefix-free Kolmogorov complexity of its initial segments is eventually unbounded. It is known that weakly 2-generic sets are shallow, i.e. not deep. In this paper, we show that there is a deep 1-generic set. |
| title | There is a deep 1-generic set |
| topic | Logic Logic in Computer Science 03D30, 68Q30 |
| url | https://arxiv.org/abs/2409.00631 |