20 citations · 56 across the 31 of their papers we have counts for
5 papers · 1 filter
Pointed computations and Martin-Löf randomness
George Barmpalias, Andrew Lewis-Pye, Angsheng Li
Schnorr showed that a real is Martin-Loef random if and only if all of its initial segments are incompressible with respect to prefix-free complexity. Fortnow and independently Nie…
Optimal redundancy in computations from random oracles
George Barmpalias, Andrew Lewis-Pye
A classic result in algorithmic information theory is that every infinite binary sequence is computable from a Martin-Loef random infinite binary sequence. Proved independently by…
Differences of halting probabilities
George Barmpalias, Andrew Lewis-Pye
The halting probabilities of universal prefix-free machines are universal for the class of reals with computably enumerable left cut (also known as left-c.e. reals), and coincide w…
Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers
George Barmpalias, Andrew Lewis-Pye, Jason Teutsch
The Kučera-Gács theorem is a landmark result in algorithmic randomness asserting that every real is computable from a Martin-Löf random real. If the computation of the first bi…
Computing halting probabilities from other halting probabilities
George Barmpalias, Andrew Lewis-Pye
The halting probability of a Turing machine is the probability that the machine will halt if it starts with a random stream written on its one-way input tape. When the machine is u…