Search

Abstract: In this paper we introduce the notion of ε-universal prefix-free Turing machine (ε is a computable real in ) 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 , some ε-random reals do not contain even arbitrarily long runs of 0s. [Copyright &y& Elsevier]