20 citations · 33 across the 29 of their papers we have counts for
Showing 2011Show all
3 papers · 1 filter
math.LO2011★ 2 cited
The typical Turing degree
George Barmpalias, Adam R. Day, Andrew E. M. Lewis
The Turing degree of a real measures the computational difficulty of producing its binary expansion. Since Turing degrees are tailsets, it follows from Kolmogorov's 0-1 law that fo…
math.LO2011★ 1 cited
Kolmogorov complexity and computably enumerable sets
George Barmpalias, Angsheng Li
We study the computably enumerable sets in terms of the: (a) Kolmogorov complexity of their initial segments; (b) Kolmogorov complexity of finite programs when they are used as ora…
math.LO2011
Universal computably enumerable sets and initial segment prefix-free complexity
George Barmpalias
We show that there are Turing complete computably enumerable sets of arbitrarily low non-trivial initial segment prefix-free complexity. In particular, given any computably enumera…