Sophistication as Randomness Deficiency (chapter)
The sophistication of a string measures how much structural information it contains. We introduce naive sophistication, a variant of sophistication based on randomness deficiency. Naive sophistication measures the minimum number of bits needed to specify a set in which the string is a typical elemen...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag Berlin Heidelberg
2014
|
| Online Access: | http://hdl.handle.net/1721.1/85842 https://orcid.org/0000-0003-1333-4045 |
| _version_ | 1826215215829614592 |
|---|---|
| author | Mota, Francisco Aaronson, Scott Antunes, Luís Souto, André |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Mota, Francisco Aaronson, Scott Antunes, Luís Souto, André |
| author_sort | Mota, Francisco |
| collection | MIT |
| description | The sophistication of a string measures how much structural information it contains. We introduce naive sophistication, a variant of sophistication based on randomness deficiency. Naive sophistication measures the minimum number of bits needed to specify a set in which the string is a typical element. Thanks to Vereshchagin and Vitányi, we know that sophistication and naive sophistication are equivalent up to low order terms. We use this to relate sophistication to lossy compression, and to derive an alternative formulation for busy beaver computational depth. |
| first_indexed | 2024-09-23T16:19:14Z |
| format | Article |
| id | mit-1721.1/85842 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:19:14Z |
| publishDate | 2014 |
| publisher | Springer-Verlag Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/858422022-09-29T19:31:43Z Sophistication as Randomness Deficiency (chapter) Mota, Francisco Aaronson, Scott Antunes, Luís Souto, André Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Aaronson, Scott The sophistication of a string measures how much structural information it contains. We introduce naive sophistication, a variant of sophistication based on randomness deficiency. Naive sophistication measures the minimum number of bits needed to specify a set in which the string is a typical element. Thanks to Vereshchagin and Vitányi, we know that sophistication and naive sophistication are equivalent up to low order terms. We use this to relate sophistication to lossy compression, and to derive an alternative formulation for busy beaver computational depth. Fundação para a Ciência e a Tecnologia (project CSI[superscript 2], reference# PTDC/EIA-CCO/099951/2008) Instituto de Telecomunicações (grant) Fundação para a Ciência e a Tecnologia (scholarship SFRH/BPD/76231/2011) 2014-03-20T14:49:22Z 2014-03-20T14:49:22Z 2013 Article http://purl.org/eprint/type/JournalArticle 978-3-642-39309-9 978-3-642-39310-5 0302-9743 1611-3349 http://hdl.handle.net/1721.1/85842 Mota, Francisco, Scott Aaronson, Luís Antunes, and André Souto. “Sophistication as Randomness Deficiency.” in Descriptional Complexity of Formal Systems: 15th International Workshop, DCFS 2013, London, ON, Canada, July 22-25, 2013. Proceedings (Lecture Notes in Computer Science; ser. vol. 8031) (2013): 172–181. https://orcid.org/0000-0003-1333-4045 en_US http://dx.doi.org/10.1007/978-3-642-39310-5_17 Descriptional Complexity of Formal Systems Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag Berlin Heidelberg MIT web domain |
| spellingShingle | Mota, Francisco Aaronson, Scott Antunes, Luís Souto, André Sophistication as Randomness Deficiency (chapter) |
| title | Sophistication as Randomness Deficiency (chapter) |
| title_full | Sophistication as Randomness Deficiency (chapter) |
| title_fullStr | Sophistication as Randomness Deficiency (chapter) |
| title_full_unstemmed | Sophistication as Randomness Deficiency (chapter) |
| title_short | Sophistication as Randomness Deficiency (chapter) |
| title_sort | sophistication as randomness deficiency chapter |
| url | http://hdl.handle.net/1721.1/85842 https://orcid.org/0000-0003-1333-4045 |
| work_keys_str_mv | AT motafrancisco sophisticationasrandomnessdeficiencychapter AT aaronsonscott sophisticationasrandomnessdeficiencychapter AT antunesluis sophisticationasrandomnessdeficiencychapter AT soutoandre sophisticationasrandomnessdeficiencychapter |