Please use this identifier to cite or link to this item:
|Title:||Representation of left-computable ε-random reals||Authors:||Calude, C.S.
ε-universal prefix-free Turing machine
|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.
checked on Apr 5, 2020
WEB OF SCIENCETM
checked on Mar 20, 2020
checked on Mar 28, 2020
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.