Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/40532
Title: Presentations of K-trivial reals and kolmogorov complexity
Authors: Stephan, F. 
Wu, G.
Issue Date: 2005
Source: Stephan, F.,Wu, G. (2005). Presentations of K-trivial reals and kolmogorov complexity. Lecture Notes in Computer Science 3526 : 461-469. ScholarBank@NUS Repository.
Abstract: For given real α ∈ {0,1} ∞, a presentation V of α is a prefix-free and recursively enumerable subset of {0,1}* such that α = ∑ σ∈V 2 -|σ|. So, α has a presentation iff α is a left-r.e. real. Let A be the class of all reals which have only computable presentations. Downey and LaForte proved that A has an incomputable member. Call α strongly Kurtz-random if there does not exist any recursive function f with K(α(0) ... α(f(n) - 1)) < f(n) - n for all n. It is shown that every α ∈ A is either computable or strongly Kurtz-random. In particular, all K-trivial members of A are computable where α is K-trivial iff there is a c such that, for all n, K(α(0) ... α(n - 1)) < K(n) + c. Thus there is a natural and nontrivial Turing ideal of left-r.e. α not containing any incomputable member of A. © Springer-Verlag Berlin Heidelberg 2005.
Source Title: Lecture Notes in Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/40532
ISSN: 03029743
Appears in Collections:Staff Publications

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

Page view(s)

53
checked on Dec 9, 2017

Google ScholarTM

Check


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