Lowness for bounded randomness
In [3], Brodhead, Downey and Ng introduced some new variations of the notions of being Martin-Löf random where the tests are all clopen sets. We explore the lowness notions associated with these randomness notions. While these bounded notions seem far from classical notions with infinite tests like...
Saved in:
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2013
|
| Online Access: | https://hdl.handle.net/10356/96557 http://hdl.handle.net/10220/10307 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| id |
sg-ntu-dr.10356-96557 |
|---|---|
| record_format |
dspace |
| spelling |
sg-ntu-dr.10356-965572020-03-07T12:34:42Z Lowness for bounded randomness Downey, Rod. Ng, Keng Meng School of Physical and Mathematical Sciences In [3], Brodhead, Downey and Ng introduced some new variations of the notions of being Martin-Löf random where the tests are all clopen sets. We explore the lowness notions associated with these randomness notions. While these bounded notions seem far from classical notions with infinite tests like Martin-Löf and Demuth randomness, the lowness notions associated with bounded randomness turn out to be intertwined with the lowness notions for these two concepts. In fact, in one case, we get a new and likely very useful characterization of K-triviality. 2013-06-13T03:20:21Z 2019-12-06T19:32:30Z 2013-06-13T03:20:21Z 2019-12-06T19:32:30Z 2012 2012 Journal Article Downey, R., & Ng, K. M. (2012). Lowness for bounded randomness. Theoretical Computer Science, 460, 1-9. 0304-3975 https://hdl.handle.net/10356/96557 http://hdl.handle.net/10220/10307 10.1016/j.tcs.2012.06.004 en Theoretical computer science © 2012 Elsevier B.V. |
| institution |
Nanyang Technological University |
| building |
NTU Library |
| country |
Singapore |
| collection |
DR-NTU |
| language |
English |
| description |
In [3], Brodhead, Downey and Ng introduced some new variations of the notions of being Martin-Löf random where the tests are all clopen sets. We explore the lowness notions associated with these randomness notions. While these bounded notions seem far from classical notions with infinite tests like Martin-Löf and Demuth randomness, the lowness notions associated with bounded randomness turn out to be intertwined with the lowness notions for these two concepts. In fact, in one case, we get a new and likely very useful characterization of K-triviality. |
| author2 |
School of Physical and Mathematical Sciences |
| author_facet |
School of Physical and Mathematical Sciences Downey, Rod. Ng, Keng Meng |
| format |
Article |
| author |
Downey, Rod. Ng, Keng Meng |
| spellingShingle |
Downey, Rod. Ng, Keng Meng Lowness for bounded randomness |
| author_sort |
Downey, Rod. |
| title |
Lowness for bounded randomness |
| title_short |
Lowness for bounded randomness |
| title_full |
Lowness for bounded randomness |
| title_fullStr |
Lowness for bounded randomness |
| title_full_unstemmed |
Lowness for bounded randomness |
| title_sort |
lowness for bounded randomness |
| publishDate |
2013 |
| url |
https://hdl.handle.net/10356/96557 http://hdl.handle.net/10220/10307 |
| _version_ |
1681042016230703104 |