Abstract:
In this paper we introduce the notion of ε–universal prefix-free Turing machine
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 Peano Arithmetic.
The theory developed here parallels to a large extent the classical theory,
but not completely.