Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.jcss.2010.08.001
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. https://doi.org/10.1016/j.jcss.2010.08.001
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
URI: http://scholarbank.nus.edu.sg/handle/10635/104619
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.

SCOPUSTM   
Citations

8
checked on Jun 13, 2018

WEB OF SCIENCETM
Citations

5
checked on Apr 24, 2018

Page view(s)

32
checked on Mar 11, 2018

Google ScholarTM

Check

Altmetric


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