20 citations · 56 across the 31 of their papers we have counts for
7 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…
A note on the differences of computably enumerable reals
George Barmpalias, Andrew Lewis-Pye
We show that given any non-computable left-c.e. real there exists a left-c.e. real such that for all left-c.e. reals and all right-c.e. reals . The proof is…
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…
Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
George Barmpalias, Nan Fang, Andrew Lewis-Pye
Chaitin's number Omega is the halting probability of a universal prefix-free machine, and although it depends on the underlying enumeration of prefix-free machines, it is always Tu…