Cover Image

Solovay functions and their applications in algorithmic randomness

Classical versions of Kolmogorov complexity are incomputable. Nevertheless, in 1975 Solovay showed that there are computable functions f≥K+O(1) such that for infinitely many strings σ, f(σ)=K(σ)+O(1), where K denotes prefix-free Kolmogorov complexity. Such an f is now called a Solovay function. We p...

Full description

Saved in:
Bibliographic Details
Main Authors: Bienvenu, Laurent (Author) , Downey, Rod (Author) , Nies, André (Author) , Merkle, Wolfgang (Author)
Format: Article (Journal)
Language:English
Published: 18 May 2015
In: Journal of computer and system sciences
Year: 2015, Volume: 81, Issue: 8, Pages: 1575-1591
ISSN:1090-2724
DOI:10.1016/j.jcss.2015.04.004
Online Access:Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1016/j.jcss.2015.04.004
Verlag, lizenzpflichtig, Volltext: http://www.sciencedirect.com/science/article/pii/S0022000015000422
Get full text
Author Notes:Laurent Bienvenu, Rod Downey, André Nies, Wolfgang Merkle

MARC

LEADER 00000caa a2200000 c 4500
001 1698758553
003 DE-627
005 20220818095540.0
007 cr uuu---uuuuu
008 200525s2015 xx |||||o 00| ||eng c
024 7 |a 10.1016/j.jcss.2015.04.004  |2 doi 
035 |a (DE-627)1698758553 
035 |a (DE-599)KXP1698758553 
035 |a (OCoLC)1341326406 
040 |a DE-627  |b ger  |c DE-627  |e rda 
041 |a eng 
084 |a 28  |2 sdnb 
100 1 |a Bienvenu, Laurent  |e VerfasserIn  |0 (DE-588)1162870516  |0 (DE-627)1026974488  |0 (DE-576)50764641X  |4 aut 
245 1 0 |a Solovay functions and their applications in algorithmic randomness  |c Laurent Bienvenu, Rod Downey, André Nies, Wolfgang Merkle 
264 1 |c 18 May 2015 
300 |a 17 
336 |a Text  |b txt  |2 rdacontent 
337 |a Computermedien  |b c  |2 rdamedia 
338 |a Online-Ressource  |b cr  |2 rdacarrier 
500 |a Gesehen am 25.05.2020 
520 |a Classical versions of Kolmogorov complexity are incomputable. Nevertheless, in 1975 Solovay showed that there are computable functions f≥K+O(1) such that for infinitely many strings σ, f(σ)=K(σ)+O(1), where K denotes prefix-free Kolmogorov complexity. Such an f is now called a Solovay function. We prove that many classical results about K can be obtained by replacing K by a Solovay function. For example, the three following properties of a function g all hold for the function K.(i)The sum of the terms ∑n2−g(n) is a Martin-Löf random real.(ii)A sequence A is Martin-Löf random if and only if g(A↾n)>n−O(1).(iii)A sequence A is K-trivial if and only if K(A↾n)<g(n)+O(1). We show that when fixing any of these three properties, then among all computable functions exactly the Solovay functions possess this property. Furthermore, this characterization extends accordingly to the larger class of right-c.e. functions. 
650 4 |a Algorithmic randomness 
650 4 |a Kolmogorov complexity 
650 4 |a Solovay functions 
700 1 |a Downey, Rod  |e VerfasserIn  |4 aut 
700 1 |a Nies, André  |e VerfasserIn  |4 aut 
700 1 |a Merkle, Wolfgang  |e VerfasserIn  |0 (DE-588)1049898400  |0 (DE-627)782852831  |0 (DE-576)40388201X  |4 aut 
773 0 8 |i Enthalten in  |t Journal of computer and system sciences  |d San Diego, Calif. [u.a.] : Elsevier, 1967  |g 81(2015), 8, Seite 1575-1591  |h Online-Ressource  |w (DE-627)26689254X  |w (DE-600)1469171-1  |w (DE-576)103373195  |x 1090-2724  |7 nnas  |a Solovay functions and their applications in algorithmic randomness 
773 1 8 |g volume:81  |g year:2015  |g number:8  |g pages:1575-1591  |g extent:17  |a Solovay functions and their applications in algorithmic randomness 
856 4 0 |u https://doi.org/10.1016/j.jcss.2015.04.004  |x Verlag  |x Resolving-System  |z lizenzpflichtig  |3 Volltext 
856 4 0 |u http://www.sciencedirect.com/science/article/pii/S0022000015000422  |x Verlag  |z lizenzpflichtig  |3 Volltext 
951 |a AR 
992 |a 20200525 
993 |a Article 
994 |a 2015 
998 |g 1049898400  |a Merkle, Wolfgang  |m 1049898400:Merkle, Wolfgang  |d 110000  |d 110300  |e 110000PM1049898400  |e 110300PM1049898400  |k 0/110000/  |k 1/110000/110300/  |p 4  |y j 
999 |a KXP-PPN1698758553  |e 3670749810 
BIB |a Y 
SER |a journal 
JSO |a {"note":["Gesehen am 25.05.2020"],"type":{"media":"Online-Ressource","bibl":"article-journal"},"recId":"1698758553","language":["eng"],"title":[{"title":"Solovay functions and their applications in algorithmic randomness","title_sort":"Solovay functions and their applications in algorithmic randomness"}],"person":[{"family":"Bienvenu","given":"Laurent","roleDisplay":"VerfasserIn","display":"Bienvenu, Laurent","role":"aut"},{"role":"aut","display":"Downey, Rod","roleDisplay":"VerfasserIn","given":"Rod","family":"Downey"},{"given":"André","family":"Nies","role":"aut","roleDisplay":"VerfasserIn","display":"Nies, André"},{"role":"aut","roleDisplay":"VerfasserIn","display":"Merkle, Wolfgang","given":"Wolfgang","family":"Merkle"}],"physDesc":[{"extent":"17 S."}],"relHost":[{"part":{"year":"2015","issue":"8","pages":"1575-1591","volume":"81","text":"81(2015), 8, Seite 1575-1591","extent":"17"},"titleAlt":[{"title":"JCSS"}],"pubHistory":["1.1967 -"],"language":["eng"],"recId":"26689254X","disp":"Solovay functions and their applications in algorithmic randomnessJournal of computer and system sciences","note":["Gesehen am 04.06.2020"],"type":{"media":"Online-Ressource","bibl":"periodical"},"title":[{"subtitle":"JCSS","title":"Journal of computer and system sciences","title_sort":"Journal of computer and system sciences"}],"physDesc":[{"extent":"Online-Ressource"}],"id":{"issn":["1090-2724"],"eki":["26689254X"],"zdb":["1469171-1"]},"origin":[{"publisherPlace":"San Diego, Calif. [u.a.] ; New York, NY [u.a.] ; San Diego, Calif. [u.a.]","dateIssuedKey":"1967","publisher":"Elsevier ; Acad. Press ; Acad. Press","dateIssuedDisp":"1967-"}]}],"origin":[{"dateIssuedDisp":"18 May 2015","dateIssuedKey":"2015"}],"id":{"doi":["10.1016/j.jcss.2015.04.004"],"eki":["1698758553"]},"name":{"displayForm":["Laurent Bienvenu, Rod Downey, André Nies, Wolfgang Merkle"]}} 
SRT |a BIENVENULASOLOVAYFUN1820 

Similar Items