1. Representation of left-computable ε-random reals
- Author
-
Calude, Cristian S., Hay, Nicholas J., and Stephan, Frank
- Subjects
- *
COMPUTABLE functions , *INTEGRAL representations , *PROBABILITY theory , *REAL numbers , *ARITHMETIC , *COMPUTATIONAL mathematics , *TURING machines - Abstract
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]
- Published
- 2011
- Full Text
- View/download PDF