20 citations · 33 across the 29 of their papers we have counts for
11 papers · 1 filter
The probability of a computable output from a random oracle
George Barmpalias, Douglas Cenzer, Christopher P. Porter
Consider a universal Turing machine that produces a partial or total function (or a binary stream), based on the answers to the binary queries that it makes during the computation.…
On the existence of a strong minimal pair
George Barmpalias, Mingzhong Cai, Steffen Lempp +1
We show that there is a strong minimal pair in the computably enumerable Turing degrees.
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…
Kobayashi compressibility
George Barmpalias, Rodney G. Downey
Kobayashi introduced a uniform notion of compressibility of infinite binary sequences in terms of relative Turing computations with sub-identity use of the oracle. Kobayashi compre…
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…
Random numbers as probabilities of machine behaviour
George Barmpalias, Douglas Cenzer, Christopher P. Porter
A fruitful way of obtaining meaningful, possibly concrete, algorithmically random numbers is to consider a potential behaviour of a Turing machine and its probability with respect…
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…