C(x) given x. Applications to left c.e. reals: Computability, Turing-completeness and computational gaps

C(x) given x. Applications to left c.e. reals: Computability, Turing-completeness and computational gaps George Davie September 2025 Most strings xreadily give their own complexity: “my length minus something small”. But some strings are complexity withholding—there is no short program that takes xand outputs C(x). These strings do not want to give their complexity; that is, there is no short program which takes xand outputs C(x). In other words, C(C(x)|x) is large. This paper reveals a surprising phenomenon: complexity withholding strings create computational gaps. Even with vastly more computational resources than should be needed, we cannot reach other strings of comparable complexity. The key lies in the waiting times inherent in computations. Before we continue, we note that there are strings xwith large C(C(x)|x). In fact, by Shen and Bauwens [3]1: for each nthere are strings of length nsuch that C(C(x)|x)≥log n−O(1). Recall that, since the length C(C(x)|x)) of such a program for xof length n is bounded from above by log n, see Li and Vit´anyi [1], this is the best possible bound. For such strings x,xitself does not help at all in finding C(x). Strings xwith large C(C(x)|x) are rare but play a central role in the theory. One example is in counterexamples to information symmetry of Kolmogorov complexity; see G´acs [9]. Also see, for example, Section 2.8 in Li and Vit´anyi [1]. We will sometimes call strings for which C(C(x)|x) is not small, complexity withholding. 1Also see this paper for references to previous work on the function C(C(x)|x). 1 Now let αand βbe left c.e. reals, (Pα, Pβ) a pair of programs generating them from below, and αn,βntheir first ndigits. It is obvious that an αncomputes aβn, if the settling time of αn—the time it takes for the approximations to the c.e. real to settle on αn—is longer than that of βn. That is, just wait for the growing approximation to αnto settle and then read off the approximation to βn—which will be the actual βn. This will follow if the Kolmogorov complexity C(αn) is sufficiently greater than C(βn). In this sense, for any two left c.e. reals, either αncomputes βnor conversely, since one must settle first. How hard is it to compute the initial segment settling last from the one settling first? Our basic observation is that there exists a small computable band d2such that, if αnis outside the band, C(αn)≥C(βn) + d, then it is often very hard, requiring a lot of extra information. In fact, we require at least around C(C(βn)|βn) extra bits. Since C(C(βn)|βn) has no finite bound, and we only want to lift the complexity by d, this is surprising. Theorem 1. For a given β, α, there is a computable number d, such that, for all n, no program of length less than C(C(βn)|βn)can transform βninto αn with C(αn)≥C(βn) + d. We will show that this fact implies sharp results around Chaitin’s characterisation of computability in terms of initial segment complexity. For example, we will show that if C(αn)≥C(n) + dfor all n, then αis Turing-complete in a very strong sense. In some sense, computable sequences are only some constant daway from being Turing-complete. We will also look at Frank Stephan’s relativisation of Chaitin’s result, in this light. Further, and most surprisingly, we will show the general difficulty of computing an initial segment αnof complexity less than βn. It will be comparably difficult even to compute any n-length string x3of complexity at least cless. Theorem 2. For a given β,α, there is a computable number dsuch that, for all n, no program of length at most C(C(βn)|βn)−2 log c−dcan transform βn into αnwith C(αn) = C(βn)−c. Since left c.e. reals are so-called limit computable, concepts of domination as in Section 3.5 of Soare [11] all apply. We have not yet explored the deeper relations with these concepts from pure computability theory. 2dnot much longer than l(Pβ) + l(Pα) 3Not necessarily an initial segment of any c.e. real. 2 References [1] Li, Ming, and P. M. Vit´anyi. 2019. An introduction to Kolmogorov complexity and its applications. Cham Springer Series: Texts in Computer Science [2] A. Kuˇcera and T. A. Slaman. Randomness and recursive enumerability. SIAM Journal on Computing, 31:199-211, 2001. [3] B. Bauwens, A. Shen, Complexity Of Complexity And Strings With Maximal Plain And Prefix Kolmogorov Complexity, The Journal of Symbolic Logic. 79 (2014) 620632. doi:10.1017/jsl.2014.15. [4] G.J. Chaitin. Information-theoretic characterizations of recursive infinite strings. Theor. Comput. Sci., 2:4548, 1976. [5] R.P. Daley. Noncomplex sequences: characterizations and examples. Journal of Symbolic Logic, 41:626-638, 1976. [6] R. G. Downey. D.R. Hirschfeldt. Algorithmic randomness and complexity, Springer Verlag 2010 [7] A. Nies. Computability and Randomness. Oxford, England: Oxford University Press UK. (2008) [8] Csima, B. F., and Shore, R. A. (2007). The settling-time reducibility ordering. Journal of Symbolic Logic, 72(3), 1055-1071. doi:10.2178/jsl/1191333856 [9] P. G´acs, On the symmetry of algorithmic information, Soviet Math. Dokl., vol. 15 (1974), pp. 1477-1480. [10] W. Merkle and F. Stephan. On C-degrees, H-degrees and T-degrees. In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC 2007). IEEE Computer Society Press, San Diego, CA, 2007. [11] Soare, R. I. Turing computability theory and applications, Springer Berlin, 2018 3