Initial segment complexities of randomness notions
Schnorr famously proved that Martin-Löf-randomness of a sequence A can be characterised via the complexity of A ʼs initial segments. Nies, Stephan and Terwijn as well as independently Miller showed that a set is 2-random (that is, Martin-Löf random relative to the halting problem K ) iff there i...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2014
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/103751 http://hdl.handle.net/10220/19262 |
| _version_ | 1811679885002801152 |
|---|---|
| author | Hölzl, Rupert Kräling, Thorsten Stephan, Frank Wu, Guohua |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Hölzl, Rupert Kräling, Thorsten Stephan, Frank Wu, Guohua |
| author_sort | Hölzl, Rupert |
| collection | NTU |
| description | Schnorr famously proved that Martin-Löf-randomness of a sequence A can be characterised via the complexity of A ʼs initial segments. Nies, Stephan and Terwijn as well as independently Miller showed that a set is 2-random (that is, Martin-Löf random relative to the halting problem K ) iff there is no function f such that for all m and all n>f(m)n>f(m) it holds that C(A(0)A(1)…A(n))⩽n−mC(A(0)A(1)…A(n))⩽n−m; before the proof of this equivalence the notion defined via the latter condition was known as Kolmogorov random.
In the present work it is shown that characterisations of this style can also be given for other randomness criteria like strong randomness (also known as weak 2-randomness), Kurtz randomness relative to K , Martin-Löf randomness of PA-incomplete sets, and strong Kurtz randomness; here one does not just quantify over all functions f but over functions f of a specific form. For example, A is Martin-Löf random and PA-incomplete iff there is no A -recursive function f such that for all m and all n>f(m)n>f(m) it holds that C(A(0)A(1)…A(n))⩽n−mC(A(0)A(1)…A(n))⩽n−m. The characterisation for strong randomness relates to functions which are the concatenation of an A-recursive function executed after a K-recursive function; this solves an open problem of Nies.
In addition to this, characterisations of a similar style are also given for Demuth randomness, weak Demuth randomness and Schnorr randomness relative to K. Although the unrelativised versions of Kurtz randomness and Schnorr randomness do not admit such a characterisation in terms of plain Kolmogorov complexity, Bienvenu and Merkle gave one in terms of Kolmogorov complexity defined by computable machines. |
| first_indexed | 2024-10-01T03:16:15Z |
| format | Journal Article |
| id | ntu-10356/103751 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:16:15Z |
| publishDate | 2014 |
| record_format | dspace |
| spelling | ntu-10356/1037512020-03-07T12:37:04Z Initial segment complexities of randomness notions Hölzl, Rupert Kräling, Thorsten Stephan, Frank Wu, Guohua School of Physical and Mathematical Sciences DRNTU::Science::Mathematics Schnorr famously proved that Martin-Löf-randomness of a sequence A can be characterised via the complexity of A ʼs initial segments. Nies, Stephan and Terwijn as well as independently Miller showed that a set is 2-random (that is, Martin-Löf random relative to the halting problem K ) iff there is no function f such that for all m and all n>f(m)n>f(m) it holds that C(A(0)A(1)…A(n))⩽n−mC(A(0)A(1)…A(n))⩽n−m; before the proof of this equivalence the notion defined via the latter condition was known as Kolmogorov random. In the present work it is shown that characterisations of this style can also be given for other randomness criteria like strong randomness (also known as weak 2-randomness), Kurtz randomness relative to K , Martin-Löf randomness of PA-incomplete sets, and strong Kurtz randomness; here one does not just quantify over all functions f but over functions f of a specific form. For example, A is Martin-Löf random and PA-incomplete iff there is no A -recursive function f such that for all m and all n>f(m)n>f(m) it holds that C(A(0)A(1)…A(n))⩽n−mC(A(0)A(1)…A(n))⩽n−m. The characterisation for strong randomness relates to functions which are the concatenation of an A-recursive function executed after a K-recursive function; this solves an open problem of Nies. In addition to this, characterisations of a similar style are also given for Demuth randomness, weak Demuth randomness and Schnorr randomness relative to K. Although the unrelativised versions of Kurtz randomness and Schnorr randomness do not admit such a characterisation in terms of plain Kolmogorov complexity, Bienvenu and Merkle gave one in terms of Kolmogorov complexity defined by computable machines. 2014-04-24T01:59:38Z 2019-12-06T21:19:20Z 2014-04-24T01:59:38Z 2019-12-06T21:19:20Z 2014 2014 Journal Article Hölzl, R., Kräling, T., Stephan, F., & Wu, G. (2014). Initial segment complexities of randomness notions. Information and Computation, 234, 57-67. 0890-5401 https://hdl.handle.net/10356/103751 http://hdl.handle.net/10220/19262 10.1016/j.ic.2013.12.002 177271 en Information and computation © 2013 Elsevier B.V. |
| spellingShingle | DRNTU::Science::Mathematics Hölzl, Rupert Kräling, Thorsten Stephan, Frank Wu, Guohua Initial segment complexities of randomness notions |
| title | Initial segment complexities of randomness notions |
| title_full | Initial segment complexities of randomness notions |
| title_fullStr | Initial segment complexities of randomness notions |
| title_full_unstemmed | Initial segment complexities of randomness notions |
| title_short | Initial segment complexities of randomness notions |
| title_sort | initial segment complexities of randomness notions |
| topic | DRNTU::Science::Mathematics |
| url | https://hdl.handle.net/10356/103751 http://hdl.handle.net/10220/19262 |
| work_keys_str_mv | AT holzlrupert initialsegmentcomplexitiesofrandomnessnotions AT kralingthorsten initialsegmentcomplexitiesofrandomnessnotions AT stephanfrank initialsegmentcomplexitiesofrandomnessnotions AT wuguohua initialsegmentcomplexitiesofrandomnessnotions |