| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4952152 | Theoretical Computer Science | 2017 | 12 Pages |
Abstract
We prove that Kobayashi compressibility can be used in order to define Martin-Löf randomness, a strong version of finite randomness and Kurtz randomness, strictly in terms of Turing reductions. Moreover these randomness notions naturally correspond to Turing reducibility, weak truth-table reducibility and truth-table reducibility respectively. Finally we discuss Kobayashi's main result from [21] regarding the compressibility of computably enumerable sets, and provide additional related original results.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
George Barmpalias, Rodney G. Downey,