{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T20:30:36Z","timestamp":1648672236655},"reference-count":14,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,9,5]],"date-time":"2014-09-05T00:00:00Z","timestamp":1409875200000},"content-version":"unspecified","delay-in-days":461,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. symb. log"],"published-print":{"date-parts":[[2013,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A Martin-L\u00f6f random sequence is an infinite binary sequence with the property that every initial segment <jats:italic>\u03c3<\/jats:italic> has prefix-free Kolmogorov complexity <jats:italic>K(\u03c3)<\/jats:italic> at least \u2223\u03c3\u2223 \u2212 <jats:italic>c<\/jats:italic>, for some constant <jats:italic>c<\/jats:italic> \u03f5 <jats:italic>\u03c9<\/jats:italic>. Informally, initial segments of Martin-L\u00f6f randoms are highly complex in the sense that they are not compressible by more than a constant number of bits. However, all Martin-L\u00f6f randoms necessarily have contiguous <jats:italic>substrings<\/jats:italic> of arbitrarily low complexity. If we demand that all substrings of a sequence be uniformly complex, then we arrive at the notion of shift-complex sequences. In this paper, we collect some of the existing results on these sequences and contribute two new ones. Rumyantsev showed that the measure of oracles that compute shift-complex sequences is zero. We strengthen this result by proving that the Martin-L\u00f6f random sequences that do not compute shift-complex sequences are exactly the incomplete ones, in other words, the ones that do not compute the halting problem. In order to do so, we make use of the characterization by Franklin and Ng of the class of incomplete Martin-L\u00f6f randoms via a notion of randomness called <jats:italic>difference randomness<\/jats:italic>. Turning to the power of shift-complex sequences as oracles, we show that there are shift-complex sequences that do not compute Martin-L\u00f6f random (or even Kurtz random) sequences.<\/jats:p>","DOI":"10.2178\/bsl.1902020","type":"journal-article","created":{"date-parts":[[2013,5,16]],"date-time":"2013-05-16T11:08:25Z","timestamp":1368702505000},"page":"199-215","source":"Crossref","is-referenced-by-count":1,"title":["Shift-complex sequences"],"prefix":"10.1017","volume":"19","author":[{"given":"Mushfeq","family":"Khan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,9,5]]},"reference":[{"key":"S1079898600008854_ref007","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/bdr003"},{"key":"S1079898600008854_ref011","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199230761.001.0001"},{"key":"S1079898600008854_ref003","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68441-3"},{"key":"S1079898600008854_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-007-0058-y"},{"key":"S1079898600008854_ref006","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-2010-10513-0"},{"key":"S1079898600008854_ref008","volume-title":"Shift complex sequences","author":"Hirschfeldt","year":"2012"},{"key":"S1079898600008854_ref013","first-page":"464","volume-title":"STACS 2011","volume":"9","author":"Rumyantsev","year":"2011"},{"key":"S1079898600008854_ref004","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1208359062"},{"key":"S1079898600008854_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.09.006"},{"key":"S1079898600008854_ref002","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1333566632"},{"key":"S1079898600008854_ref009","volume-title":"Bushy tree forcing","author":"Khan"},{"key":"S1079898600008854_ref012","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_32"},{"key":"S1079898600008854_ref014","first-page":"342","volume-title":"Logic Colloquium '02","volume":"27","author":"Stephan","year":"2006"},{"key":"S1079898600008854_ref010","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-2011-11000-1"}],"container-title":["The Bulletin of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1079898600008854","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T17:33:53Z","timestamp":1556040833000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1079898600008854\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["S1079898600008854"],"URL":"https:\/\/doi.org\/10.2178\/bsl.1902020","relation":{},"ISSN":["1079-8986","1943-5894"],"issn-type":[{"value":"1079-8986","type":"print"},{"value":"1943-5894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,6]]}}}