Searching for shortest and least programs
The Kolmogorov complexity of a string x is defined as the length of a shortest program p of x for some appropriate universal machine U, that is, U(p)=x and p is a shortest string with this property. Neither the plain nor the prefix-free version of Kolmogorov complexity are recursive but for both ver...
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
2020
|
| In: |
Theoretical computer science
Year: 2019, Jahrgang: 807, Pages: 114-127 |
| ISSN: | 1879-2294 |
| DOI: | 10.1016/j.tcs.2019.10.011 |
| Online-Zugang: | Resolving-System, lizenzpflichtig, Volltext: https://doi.org/10.1016/j.tcs.2019.10.011 Verlag, lizenzpflichtig, Volltext: http://www.sciencedirect.com/science/article/pii/S0304397519306401 
|
| Verfasserangaben: | Cristian S. Calude, Sanjay Jain, Wolfgang Merkle, Frank Stephan |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1694154076 | ||
| 003 | DE-627 | ||
| 005 | 20220818032316.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 200407r20202019xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1016/j.tcs.2019.10.011 |2 doi | |
| 035 | |a (DE-627)1694154076 | ||
| 035 | |a (DE-599)KXP1694154076 | ||
| 035 | |a (OCoLC)1341313751 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 28 |2 sdnb | ||
| 100 | 1 | |a Calude, Cristian |d 1952- |e VerfasserIn |0 (DE-588)120988259 |0 (DE-627)081013167 |0 (DE-576)292483910 |4 aut | |
| 245 | 1 | 0 | |a Searching for shortest and least programs |c Cristian S. Calude, Sanjay Jain, Wolfgang Merkle, Frank Stephan |
| 264 | 1 | |c 2020 | |
| 300 | |a 14 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Available online 15 October 2019 | ||
| 500 | |a Gesehen am 07.04.2020 | ||
| 520 | |a The Kolmogorov complexity of a string x is defined as the length of a shortest program p of x for some appropriate universal machine U, that is, U(p)=x and p is a shortest string with this property. Neither the plain nor the prefix-free version of Kolmogorov complexity are recursive but for both versions it is well-known that there are recursive exact Solovay functions, that is, recursive upper bounds for Kolmogorov complexity that are infinitely often tight. Let a coding function for a machine M be a function f such that f(x) is always a program of x for M. From the existence of exact Solovay functions it follows easily that for every universal machine there is a recursive coding function that maps infinitely many strings to a shortest program. Extending a recent line of research, in what follows it is investigated in which situations there is a coding function for some universal machine that maps infinitely many strings to the length-lexicographically least program. The main results which hold in the plain as well as in the prefix-free setting are the following. For every universal machine there is a recursive coding function that maps infinitely many strings to their least programs. There is a partial recursive coding function (defined in the natural way) for some universal machine that for every set maps infinitely many prefixes of the set to their least programs. Exactly for every set that is Bennett shallow (not deep), there is a recursive coding function for some universal machine that maps all prefixes of the set to their least programs. Differences between the plain and the prefix-free frameworks are obtained by considering effective sequences I1,I2,… of mutually disjoint finite sets and asking for a recursive coding function for some universal machine that maps at least one string in each set In to its least code. Such coding functions do not exist in the prefix-free setting but exist in the plain setting in case the sets In are not too small. | ||
| 534 | |c 2019 | ||
| 650 | 4 | |a Algorithmic Information Theory | |
| 650 | 4 | |a Bennett shallow set | |
| 650 | 4 | |a Kolmogorov complexity | |
| 650 | 4 | |a Least program | |
| 650 | 4 | |a Recursion theory | |
| 650 | 4 | |a Recursive coding function | |
| 650 | 4 | |a Shortest program | |
| 650 | 4 | |a Universal Turing machine | |
| 700 | 1 | |a Jain, Sanjay |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 | |
| 700 | 1 | |a Stephan, Frank |e VerfasserIn |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Theoretical computer science |d Amsterdam [u.a.] : Elsevier, 1975 |g 807(2020), Seite 114-127 |h Online-Ressource |w (DE-627)265784174 |w (DE-600)1466347-8 |w (DE-576)074891030 |x 1879-2294 |7 nnas |a Searching for shortest and least programs |
| 773 | 1 | 8 | |g volume:807 |g year:2020 |g pages:114-127 |g extent:14 |a Searching for shortest and least programs |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.tcs.2019.10.011 |x Resolving-System |x Verlag |z lizenzpflichtig |3 Volltext |
| 856 | 4 | 0 | |u http://www.sciencedirect.com/science/article/pii/S0304397519306401 |x Verlag |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20200407 | ||
| 993 | |a Article | ||
| 994 | |a 2020 | ||
| 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 3 | ||
| 999 | |a KXP-PPN1694154076 |e 3619705984 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"id":{"eki":["1694154076"],"doi":["10.1016/j.tcs.2019.10.011"]},"origin":[{"dateIssuedKey":"2020","dateIssuedDisp":"2020"}],"name":{"displayForm":["Cristian S. Calude, Sanjay Jain, Wolfgang Merkle, Frank Stephan"]},"relHost":[{"recId":"265784174","language":["eng"],"type":{"media":"Online-Ressource","bibl":"periodical"},"note":["Gesehen am 12.04.23"],"disp":"Searching for shortest and least programsTheoretical computer science","part":{"year":"2020","pages":"114-127","volume":"807","text":"807(2020), Seite 114-127","extent":"14"},"pubHistory":["1.1975/76 - 412.2011; Vol. 413.2012 -"],"title":[{"title_sort":"Theoretical computer science","subtitle":"the journal of the EATCS","title":"Theoretical computer science"}],"physDesc":[{"extent":"Online-Ressource"}],"id":{"zdb":["1466347-8"],"eki":["265784174"],"issn":["1879-2294"]},"origin":[{"publisher":"Elsevier","dateIssuedKey":"1975","dateIssuedDisp":"1975-","publisherPlace":"Amsterdam [u.a.]"}]}],"physDesc":[{"extent":"14 S."}],"title":[{"title_sort":"Searching for shortest and least programs","title":"Searching for shortest and least programs"}],"person":[{"family":"Calude","given":"Cristian","display":"Calude, Cristian","roleDisplay":"VerfasserIn","role":"aut"},{"family":"Jain","given":"Sanjay","display":"Jain, Sanjay","roleDisplay":"VerfasserIn","role":"aut"},{"role":"aut","roleDisplay":"VerfasserIn","display":"Merkle, Wolfgang","given":"Wolfgang","family":"Merkle"},{"role":"aut","roleDisplay":"VerfasserIn","display":"Stephan, Frank","given":"Frank","family":"Stephan"}],"language":["eng"],"recId":"1694154076","note":["Available online 15 October 2019","Gesehen am 07.04.2020"],"type":{"media":"Online-Ressource","bibl":"article-journal"}} | ||
| SRT | |a CALUDECRISSEARCHINGF2020 | ||