Representation of left-computable ε-random reals

摘要

In this paper we introduce the notion of ε-universal prefix-free Turing machine (ε is a computable real in (0,1]) and study its halting probability. The main result is the extension of the representability theorem for left-computable random reals to the case of ε-random reals: a real is left-computable ε-random iff it is the halting probability of an ε-universal prefix-free Turing machine. We also show that left-computable ε-random reals are provable ε-random in the Peano Arithmetic. The theory developed here parallels to a large extent the classical theory, but not completely. For example, random reals are Borel normal (in any base), but for ε∈(0,1), some ε-random reals do not contain even arbitrarily long runs of 0s.