Please use this identifier to cite or link to this item:
Title: Representation of left-computable ε-random reals
Authors: Calude, C.S.
Hay, N.J.
Stephan, F. 
Keywords: ε-random real
ε-universal prefix-free Turing machine
Halting probability
Peano Arithmetic
Issue Date: Jul-2011
Citation: Calude, C.S., Hay, N.J., Stephan, F. (2011-07). Representation of left-computable ε-random reals. Journal of Computer and System Sciences 77 (4) : 812-819. ScholarBank@NUS Repository.
Abstract: 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. © 2010 Elsevier Inc. All rights reserved.
Source Title: Journal of Computer and System Sciences
ISSN: 00220000
DOI: 10.1016/j.jcss.2010.08.001
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Apr 5, 2020


checked on Mar 20, 2020

Page view(s)

checked on Mar 28, 2020

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.