--- abstract: 'An index $e$ in a numbering of partial-recursive functions is called minimal if every lesser index computes a different function from $e$. Since the 1960's it has been known that, in any reasonable programming language, no effective procedure determines whether or not a given index is minimal. We investigate whether the task of determining minimal indices can be solved in an approximate sense. Our first question, regarding the set of minimal indices, is whether there exists an algorithm which can correctly label 1 out of $k$ indices as either minimal or non-minimal. Our second question, regarding the function which computes minimal indices, is whether one can compute a short list of candidate indices which includes a minimal index for a given program. We give some negative results and leave the possibility of positive results as open questions.' author: - | Jason Teutsch[^1]\ *Ben-Gurion University*\ [nsimpson@example.com](nsimpson@example.com) - | Marius Zimand[^2]\ *Towson University*\ [nsimpson@example.com](nsimpson@example.com) bibliography: - 'approximating\_min.bib' title: On approximate decidability of minimal programs --- Occam's razor for algorithms ============================ In any reasonable programming system, one can code a computable function many different ways. The shortest such code has practical value, theoretical significance, and philosophical allure. Despite their implicit appeal to simplicity, shortest codes remain elusive. Indeed no algorithm can enumerate more than finitely many shortest codes @Blu67 [@Sch98], and, as a particular consequence, there is no effective way to obtain or to recognize a shortest code.[^3] Shortest descriptions of finite strings exhibit similar ineffectivity phenomena. It is well known that any algorithm can enumerate at most finitely many strings of high complexity @LV08, that no unbounded computable function is a lower bound for Kolmogorov complexity @ZL70, and that any algorithm mapping a string to a list of values containing its Kolmogorov complexity must, for all but finitely many lengths $n$, include in the list for some string of length $n$ at least a fixed fraction of the lengths below $n+O(1)$ @BBFFGLMST06. This paper adds to this list of inapproximability results that the set of Kolmogorov random strings is not $(1,k)$-recursive for any $k$ (Theorem \[thm: howfatisshe\]). In contrast, several recent works @BMVZ13 [@BZ14; @Teu14; @Zim14] have revealed that a certain type of approximation, called *list approximation*, can be obtained for shortest descriptions of strings in a surprisingly efficient way. In list approximation, instead of achieving the ideal objective of constructing an object that has some coveted property, we are content if we at least can construct a short list (of "suspects") guaranteed to contain such an object. Bauwens, Makhlin, Vereshchagin, and Zimand @BMVZ13 showed that there is a computable function which maps strings to quadratic-length lists of strings such that one element in the list is a description of the given string with minimal length (within an additive constant). Moreover, similar lists with slightly weaker parameters can actually be constructed in polynomial time. Teutsch @Teu14, Zimand @Zim14 and Bauwens and Zimand @BZ14 have obtained polynomial-time constructions with improved parameters. In the wake of these recent positive results for finite strings, it is natural to ask whether such list approximations transfer to the semantic case of partial-recursive functions. This paper investigates this question and also the $(1,k)$-recursiveness of the set of minimal programs, which might be viewed as the decidability analog of list approximation for sets. The shortest program of a function depends on the programming system. Formally, a programming system is a *numbering* ${\varphi}$, given by a partial-recursive function $U$ mapping pairs of natural numbers to natural numbers. For every $e \geq 0$, the $e$-th function in the numbering, denoted ${\varphi}_e$, is defined as ${\varphi}_e(x) = U(e,x)$. The main objects of interest in this paper are defined as follows. Let ${\varphi}$ be a numbering. 1. ${\mathrm{MIN}}_{\varphi}= \{e \colon (\forall j<e)\: [{\varphi}_j \neq {\varphi}_e]\}$ is the *set of ${\varphi}$-minimal indices*. 2. The function ${{\textstyle\mathop{\mathrm{min}}}}_{\varphi}(e)$ denotes the unique index $j \in {\mathrm{MIN}}_{\varphi}$ such that ${\varphi}_j = {\varphi}_e$. #### Numberings. There are many effective ways to enumerate partial-recursive functions. If we want a meaningful notion of "shortest program," then at the very least we should consider only *universal* numberings, that is, numberings which include all partial-recursive functions. This class of numberings still contains pathologies, such as the Friedberg numberings @Fri58 [@Kum90]. In a Friedberg numbering every partial-recursive function has a unique index, and hence every index is minimal. In computability theory one typically uses *acceptable numberings* (also known as *Gödel numberings*), and previous studies of minimal indices focused on this type of numberings. We recall that a numbering ${\varphi}$ is called *acceptable* if for every further numbering $\psi$ there exists a recursive function $f$ (the "translation function") such that ${\varphi}_{f(e)} = \psi_e$ for all $e$. During this investigation we have observed that, despite appeals to the Recursion Theorem and hardness of index sets in prior literature, the effectiveness of the translation function for acceptable numberings seems to serve as a red herring when dealing with minimal indices. Many basic results involving acceptable numberings continue to hold if we merely require a computable bound on the output of the translation function. Consequently, we introduce the following type of numbering. \[d:cbnumbering\] A numbering ${\varphi}$ is called *computably bounded* if for any further numbering $\psi$, there exists a computable function $f$ such that for any $e$, ${\varphi}_j = \psi_e$ for some $j \leq f(e)$. Robust results require an absolute definition of "shortest program" in which computability properties do not depend on the underlying numbering. *Kolmogorov* numberings capture this notion. An acceptable numbering ${\varphi}$ is called a *Kolmogorov* numbering if for every further numbering $\psi$ the corresponding *translation* function $f$ is linearly bounded, that is there exists a positive constant $c$ such that for every index $e$, $f(e) \leq ce + c$. The standard universal Turing machine @Soa87 [@Tur36] is an example of a Kolmogorov numbering. The point is that if we define ${{\left|e\right|}}$, the length of the "program" $e$, as $\log e$, then ${{\left|f(e)\right|}} \leq {{\left|e\right|}} + O(1)$, and therefore if ${\varphi}$ is a Kolmogorov numbering and $\psi$ is an arbitrary numbering, then for every index $e$, ${{\left|{{\textstyle\mathop{\mathrm{min}}}}_{\varphi}(e)\right|}} \leq {{\left|{{\textstyle\mathop{\mathrm{min}}}}_\psi(e)\right|}} +O(1)$ where the constant $O(1)$ depends only on the linear translation function from $\psi$ to ${\varphi}$. These same inequalities hold when the translation function $f$ is linear but not necessarily recursive. Such a numbering, where the translation function is linearly bounded but not necessarily recursive, is said to have the *Kolmogorov property*. Numberings with the Kolmogorov property are sometimes referred to as *optimal* because, as we have observed with universal machines for Kolmogorov complexity, any numbering can be translated into it with a constant overhead increase in program length. Previously, Jain, Stephan, and Teutsch @JST11 investigated Turing degrees for sets of minimal indices with respect to numberings with the Kolmogorov property. We conclude our discussion on numberings by separating the notions of acceptable numbering and numbering with the Kolmogorov property. The reader may want to read first the "Notation and basic prerequisites" paragraph at the end of this section. \[Stephan\] A numbering with the Kolmogorov property need not be acceptable, and vice versa. First, let us observe that an acceptable numbering need not have the Kolmogorov property. For any acceptable ${\varphi}$, the numbering $\psi$ given by $\psi_{2^e} = {\varphi}_e$ and where non-powers of two $\psi$-indices give the everywhere divergent function is an acceptable numbering which does not have the Kolmogorov property. Indeed, for any index $e \in {\mathrm{MIN}}_{\varphi}$ besides the minimal index for the everywhere divergent function, the least $\psi$-index which computes ${\varphi}_e$ is $2^e$. Therefore no linearly bounded translation function from ${\varphi}$ to $\psi$ exists. Next we construct a numbering with the Kolmogorov property which is not acceptable. Let $A = \lim A_s$ be a limit-computable @Soa87, bi-immune set, for example Chaitin's Omega @DH10 [@LV08]. Let ${\varphi}$ be a numbering with the Kolmogorov property, and define a further numbering $\psi$ by $$\psi_{2e}= \begin{cases} {\varphi}_e &\text{if $e \in A$, and} \\ \text{some function with finite domain} &\text{otherwise,} \end{cases}$$ and similarly for $\psi_{2e+1}$ but with "$e \in A$" replaced with "$e \notin A$." This can be done by setting $\psi_{2e,s} = {\varphi}_{e,s}$ at stages $s$ where $e \in A_s$ and making $\psi_{2e+1,s} = {\varphi}_{e,s}$ when $e \notin A_s$. In the other stages, we simply freeze the computations of $\psi_{2e}$ or $\psi_{2e+1}$. Since $A$ is limit-computable, after some finitely stage, one of $\psi_{2e}$ and $\psi_{2e+1}$ becomes permanently frozen and the other function goes on to compute ${\varphi}_e$. Now the translation bound for $\psi$ is at most twice the translation bound for ${\varphi}$, hence $\psi$ has the Kolmogorov property. On the other hand, $\psi$ cannot be acceptable. Suppose that there were some computable function $f$ such that $\psi_{f(x)}$ is the everywhere constant $x$ function. Note that if $f(x)$ is even, $f(x)/2 \in A$, and if $f(x)$ is odd, then $(f(x)-1)/2 \notin A$. Now infinitely often the index $f(x)$ must either be even or odd, contradicting that $A$ is bi-immune. #### Our results and paper roadmap. As already mentioned, we seek to understand to what extent and for which type of numberings ${{\textstyle\mathop{\mathrm{min}}}}_{\varphi}$ is list approximable and/or ${\mathrm{MIN}}_{\varphi}$ is $(1,k)$-recursive. The notion of list approximability of functions has been already explained. We now define the other type of approximability in a slightly generalized form. Below we use $\chi_A$ to denote the characteristic function for the set $A$. A set of integers $A$ is called $(m,k)$-recursive if there exists a computable function mapping $k$-tuples of strings to labels $\{0,1\}^k$ such that for every tuple $(x_1, \ldots, x_k)$ the vectors $(\chi_A(x_1), \dotsc, \chi_A(x_k))$ and $f(x_1, \dotsc, x_k)$ coincide in at least $m$ positions (i.e., at least $m$ of the labels are correct if we interpret $0$ as "not-in $A$" and $1$ as "in A.") We formalize the two main problems investigated in this paper, and describe our contribution. In his Masters thesis, a survey article on minimal indices, Schaefer posed the following problem. \[@Sch98\] \[ques: schaefer's problem\] Does there exist an acceptable numbering ${\varphi}$ and a positive integer $k$ such that ${\mathrm{MIN}}_{\varphi}$ is $(1,k)$-recursive? Schaefer showed that there exists a Kolmogorov numbering $\psi$ such that ${\mathrm{MIN}}_\psi$ is not $(1,k)$-recursive for any $k$. In Section \[s:minset\], we extend his existential result to all numberings with the Kolmogorov property (Theorem \[t:onekrec\]). Schaefer showed that for any acceptable numbering ${\varphi}$, ${\mathrm{MIN}}_{\varphi}$ is not $(1,2)$-recursive, but his original problem for the case $k > 2$ remains open. The second problem, which we dub the *shortlist problem for functions* is as follows: \[ques: poly-log list\] Let ${\varphi}$ be a numbering with the Kolmogorov property. Does there exist a computable function which maps each index $e$ to a $\operatorname{poly}({{\left|e\right|}})$-size list containing an index $j$ such that ${\varphi}_e = {\varphi}_j$ and ${{\left|j\right|}} \leq {{\left|{{\textstyle\mathop{\mathrm{min}}}}_{\varphi}(e)\right|}} + O(\log {{\left|e\right|}})$? Ideally, we would like to replace the overhead "$O(\log {{\left|e\right|}})$" above with "$O(1)$," however determining whether either of these bounds is possible appears to be outside the reach of present techniques. By "polynomial-size list" we mean a finite set having cardinality bounded by a polynomial in ${{\left|e\right|}}$, but the question is interesting for any non-trivial list size. Our main results are proved in Section \[s:minf\]: - If ${\varphi}$ is an acceptable numbering and a computable function on input $e$ returns a list containing the minimal ${\varphi}$-index for ${\varphi}_e$, then the size of that list cannot be constant (Theorem \[thm:listlength2\]). - For every numbering ${\varphi}$ with the Kolmogorov property, if a computable function on input $e$ returns a list containing the minimal ${\varphi}$-index for ${\varphi}_e$, then the size of the list must be $\Omega(\log^2 e)$ (Theorem \[t:quadbound\]). - There exists a Kolmogorov numbering ${\varphi}$ such that if a computable function on input $e$ returns a list containing the minimal ${\varphi}$-index for ${\varphi}_e$, then the size of that list must be $\Omega(e)$ (Theorem \[t:expbound\]). In summary, our results show that a computable list that contains the minimal index cannot be too small. Along the lines of the second result (Theorem \[t:quadbound\]), we formulate the following question whose finite string version has a positive answer @BMVZ13: \[ques: quadshort\] Does there exist a Kolmogorov numbering ${\varphi}$ with a computable list that contains ${{\textstyle\mathop{\mathrm{min}}}}_{\varphi}(e)$ and has size $O(\log^2 e)$? A positive answer to Question \[ques: quadshort\] would immediately yield a positive answer to Question \[ques: poly-log list\] when restricted to Kolmogorov numberings but not necessarily in general since the Kolmgorov property does not permit us to translate indices effectively. These results have analogues if, roughly speaking, we substitute (computable function, minimal index) with (finite string, Kolmogorov complexity) and they are easier to establish in the latter setting. We obtain the results above by building bridges between the two settings, as we explain in Section \[s:tech\], with several technical lemmas. In particular, Lemma \[lem:pdl\] provides a connection between between Schaefer's problem and the shortlist problem for functions (Question \[ques: schaefer's problem\] and Question \[ques: poly-log list\]), as this lemma is used in the proofs for both Theorem \[t:onekrec\] and Theorem \[t:expbound\]. Finally, in Section \[s:compbound\], we extend some results from the literature regarding ${\mathrm{MIN}}_{\varphi}$ from acceptable numberings to computably bounded numberings. If ${\varphi}$ is an acceptable numbering, it is known that ${\mathrm{MIN}}_{\varphi}$ is immune @Blu67, is Turing equivalent to the jump of the halting problem @Mey72, and is not $(1,2)$-recursive @Sch98. We show that all this properties continue to hold if ${\varphi}$ is a computably bounded numbering. #### Notation and basic prerequisites. For sets $A$ and $B$, we write $A \leq_{\mathrm{T}}B$ if $A$ is Turing reducible to $B$, that is, if $A$ can be computed using the set $B$ as an oracle, and we say $A$ is $B$-computable. $A {\mathrel{\oplus}}B$ denotes the set $\{2x \colon x \in A\} \cup \{2x+1 \colon x \in B\}$. $K$ is the halting set. A set $A$ is called *$\Sigma^0_2$* if there exists computable predicate $P$ such that $x \in A \iff (\exists y)\: (\forall z)\: [P(x,y,z)]$, and $A$ is *$\Pi^0_2$* if a similar condition holds with the quantifiers reversed. $A$ is $\Delta^0_2$ if it is both $\Sigma^0_2$ and $\Pi^0_2$, or equivalently by Post's Theorem, $A \leq_{\mathrm{T}}K$. An infinite set is called *immune* if there is no algorithm which enumerates infinitely many of its members. A set is *bi-immune* if both the set and its complement are immune. A set $A$ is limit-computable if there exists a computable sequence of sets $A_s$ such that $\lim_s A_s = A(x)$. Throughout this paper, we use ${\varphi}_{e,s}$ to denote the computation of ${\varphi}_e$ up to $s$ steps, and it may happen that ${\varphi}_e$ does not converge within $s$ steps. For more details on these notions, see @Soa87. Throughout this exposition, we fix a universal machine $U$ and use $C(x) = {{\textstyle\mathop{\mathrm{min}}}}\{{{\left|p\right|}} \colon U(p) = x\}$ to denote the Kolmogorov complexity of a string $x$. Here ${{\left|p\right|}}$ denotes $\log p$, the length of the program $p$. Similarly we will use $C(x \mid y) = {{\textstyle\mathop{\mathrm{min}}}}\{{{\left|p\right|}} \colon U(p,y) = x\}$ to denote the *conditional complexity of $x$ given $y$*. Further background on Kolmogorov complexity can be found in the standard textbook by Li and Vitányi @LV08, as well as the forthcoming textbook by Shen and Vereshchagin @SV14. An *order* is an unbounded, nondecreasing function from ${\mathbb{N}}$ to ${\mathbb{N}}$. Proof techniques linking the shortest descriptions of strings and functions {#s:tech} =========================================================================== We start with a result that illustrates some of the proof techniques that we use later in more complicated settings. #### Warm up: a winner-goes-on tournament. {#sec:wgo} We show here that the *set of strings with randomness deficiency 1*, $D = \{ x \colon C(x) \geq {{\left|x\right|}}-1\}$, is not $(1,2)$-recursive. First, note that more than half of the strings at each length must belong to $D$ because there are $2^n$ strings of length $n$ and at most $2^0+ 2^1 + \dotsc 2^{n-2} = 2^{n-1} - 1$ strings with randomness deficiency less than 1. Suppose there were a computable function $f \colon \{0,1\}^2 \to \{{\mathsf{L}},{\mathsf{H}}\}^2$ witnessing that $D$ is $(1,2)$-recursive, where "${\mathsf{L}}$" is the label for low complexity (deficiency greater than 1), and "${\mathsf{H}}$" is the label for high complexity. We shall show that for every $n$, there is a string $x \in D$ of length $n$ such that $C(x) < \log n + O(1)$. Consider the restriction of $f$ to strings of length $n$, and suppose that some pair of binary strings $(x,y)$ of length $n$ receives the label $({\mathsf{H}},{\mathsf{H}})$ from $f$. Then by definition of $f$, either $x$ or $y$ must have high complexity. But when $(x,y)$ is the lexicographically least pair of strings of length $n$ satisfying $f(x,y) = ({\mathsf{H}},{\mathsf{H}})$, we can compute either $x$ or $y$ with a single advice bit given the length $n$. It follows that the Kolmogorov complexities for $x$ and $y$ are bounded by $\log n + O(1)$, which for sufficiently large $n$ contradicts that one of them has randomness deficiency less than 1. Thus it suffices to assume that the only labels which occur among pairs of binary strings with length $n$ are $({\mathsf{L}},{\mathsf{H}})$, $({\mathsf{H}},{\mathsf{L}})$, and $({\mathsf{L}},{\mathsf{L}})$. We say that a set of strings $S$ of length $n$ form a *clique* if every pair of distinct vertices $(x,y) \in S$ receive either the label $({\mathsf{L}},{\mathsf{H}})$ or $({\mathsf{H}},{\mathsf{L}})$. Fix $S$ as the lexicographically least clique which contains more than half of the strings of length $n$. Such a clique must exist because the set $D$ restricted to strings of length $n$ forms a clique. Furthermore any clique which contains more than half of the strings of length $n$ must contain a string of high complexity since most strings have high complexity. At this point, we can limit our search for a complex string to the clique $S$ where only the labels $({\mathsf{L}},{\mathsf{H}})$ and $({\mathsf{H}},{\mathsf{L}})$ occur. We run a "winner-goes-on" tournament on $S$. A *match* consists of a pair of strings, and the *winner* of a match is the string labeled "${\mathsf{H}}$." The *tournament* proceeds as follows. We start with an arbitrary pair of of strings, and the winner of that match faces the next *challenger*, a string which has not yet appeared in the tournament. The winner of this second match goes on to face the subsequent challenger, and the tournament ends once all strings have appeared in the tournament at least once, that is, when we run out of new challengers. The final winner of this tournament has high complexity. Indeed, at some point in the tournament, a string with high complexity must enter then tournament, and thereafter the winner always has high complexity. But we can describe this string of high complexity using $\log n + O(1)$ bits, a contradiction. Therefore no such function $f$ exists. Some of the main ideas used in the proof of the "warm-up" can be replicated for minimal indices. There are two key points in that proof. The first one is that all the elements of the set we show is not $(1,2)$-recursive have high Kolmogorov complexity. In Section \[s:kolmindices\], we observe that minimal indices also have relatively high Kolmogorov complexity. The second key point is that the tournament is played among the elements of a simple set (namely the set of $n$-bit strings) that has a high density (namely at least $1/2$) of strings with high complexity. In Section \[s:highdensity\], we show that minimal indices in numberings that have the Kolmogorov property satisfy a similar density condition. Finally, in Section \[s:champion\], we show that an extension of the "tournament" argument from the "warm-up" can be used to show that certain sets are not $(1,k)$-recursive. The Kolmogorov complexity of minimal indices {#s:kolmindices} -------------------------------------------- We observe that the elements of ${\mathrm{MIN}}_{\varphi}$ have relatively high Kolmogorov complexity. \[lem:okra\] For every computably bounded numbering ${\varphi}$, there exists a computable order $g$ such that $C(x) \geq g(x)$ for all $x \in {\mathrm{MIN}}_{\varphi}$. Let $U$ be the underlying universal machine for the Kolmogorov complexity function $C$. Define a numbering $\psi$ by $$\psi_q = {\varphi}_{U(q)},$$ let $t$ be a "translator" program such ${\varphi}_{t(q)} = \psi_{q}$, and let $s$ a computable function such that $t(q) \leq s(q)$ for all $q$. Let $g$ be the computable function defined as follows: $g(x)$ is the smallest $y$ such that $s(y) \geq x$. Now let $x \in {\mathrm{MIN}}_{\varphi}$ and suppose that $C(x) < g(x)$. This means that there exists $p < g(x)$ such that $U(p)=x$. Note that $t(p) \leq s(p) < x$ and ${\varphi}_{t(p)} = \psi_p = {\varphi}_{U(p)} = {\varphi}_x$. This contradicts that $x$ is a minimal ${\varphi}$-index. In the case of numberings with the Kolmogorov property we obtain better bounds. \[l:highmin\] If ${\varphi}$ has the Kolmogorov property, then for all $x \in {\mathrm{MIN}}_{\varphi}$ it holds that $C(x) \geq {{\left|x\right|}} - \log {{\left|x\right|}}$. Let $m = {{\left|x\right|}}$. Since $x$ is written on $m$ bits, we have $x \geq 2^{m-1}$. Suppose $C(x) < m - \log m$. Then there exists $p$ of length less than $m - \log m$ such that $U(p)=x$. Define a numbering $\psi$ by $$\psi_q = {\varphi}_{U(q)}.$$ Since ${\varphi}$ has the Kolmogorov property, there exists a constant $c$ such that for some $$v < cp + c \leq c 2^{m - \log m} + c < 2^{m-1} \leq x$$ it holds that ${\varphi}_v = \psi_p = {\varphi}_{U(p)} = {\varphi}_x$. This contradicts that $x \in {\mathrm{MIN}}_{\varphi}$. Sets of low complexity with high density of minimal indices {#s:highdensity} ----------------------------------------------------------- Among the strings of a given length, a large fraction are incompressible or close to incompressible. We show here that for numberings with Kolmogorov property and for a generalization of such numberings, which we call *polynomially-bounded numberings*, minimal indices have a similar property. As we shall see, there exist infinitely many finite sets of low complexity whose vast majority of elements are minimal indices. Such families of sets will be used several times in this work. \[d:polynumbering\] A numbering ${\varphi}$ is called *polynomially bounded* if for any further numbering $\psi$, there exist positive integers $k$ and $c$ such that for any $e$, ${\varphi}_j = \psi_e$ for some $j \leq ce^k + c$. We note that a numbering which is polynomially bounded with parameter $k=1$ has the Kolmogorov property and that only the case $k=1$ is used in the rest of the paper. The following "one-dimensional" version of ${\mathrm{MIN}}_{\varphi}$ will be used throughout our paper. For every numbering ${\varphi}$, we define the following subset of ${\varphi}$-minimal indices. $$M_{\varphi}= \{e : e \in {\mathrm{MIN}}_{\varphi}\text{ and ${\varphi}_e$ converges only on input~0}\}.$$ The following lemma estimates the fraction of indices which are minimal in a large interval. \[l:polyintervalbinary\] Let ${\varphi}$ be a polynomially bounded numbering with degree $p$, and let $d(k) = p^{k-1} + p^{k-2} + \dotsb + 1$. Then there exists a positive integer $a$ such that for every sufficiently large $n$ the interval $I_n =\{2^{ad(n)}+1, \dotsc, 2^{ad(n+1)}\}$ satisfies $${{\left|M_{\varphi}\cap I_n\right|}} > 2^{-ap^{n}}\cdot {{\left|I_n\right|}}.$$ When ${\varphi}$ has the Kolmogorov property, that is when $p=1$, $M_{\varphi}\cap I_n$ occupies at least constant fraction of the indices in $I_n$. Let $\psi_0, \psi_1, \ldots$ be the following numbering of all p.c. functions which are only defined at 0: $\psi_x(0) = x$, and $\psi_x(y)\uparrow$ for all $y \geq 1$. Let $c$ be the positive constant guaranteed by the degree $p$ polynomial bound so that for any index $e \geq 1$, there exists $j<ce^p$ such that ${\varphi}_j = \psi_e$ and also $\psi_0 = {\varphi}_j$ for some $j \leq c$. Fix $a=p + \lceil \log c \rceil$, and let $I_n = \{2^{ad(n)}+1, \dotsc, 2^{ad(n+1)}\}$. Each of the functions $\psi_0, \psi_1, \ldots, \psi_{2^{ad(n)+1}}$ has a minimal ${\varphi}$-index bounded by $$c (2^{ad(n)+1})^p = c 2^p 2^{p\cdot a d(n)} \leq 2^a 2^{a\cdot p d(n)} = 2^{ad(n+1)} = \max I_n.$$ It follows that at least $(2^{ad(n)+1}+1) - {{\textstyle\mathop{\mathrm{min}}}}I_n = 2^{ad(n)}$ of these minimal ${\varphi}$-indices must lie in $I_n$. Since $$\frac{{{\left|M_{\varphi}\cap I_n\right|}}}{{{\left|I_n\right|}}} \geq \frac{2^{ad(n)}}{2^{ad(n+1)} - 2^{ad(n)}} = \frac{1}{2^{ap^{n}}-1},$$ the conclusion follows. Next we show that with a small amount of advice (constant advice in the case of the Kolmogorov property), we can shrink the intervals from the previous lemma so that the resulting set contains a high concentration of minimal indices. \[polynomial density-boosting\] \[lem:pdl\] Let ${\varphi}$ be a polynomially bounded numbering with degree $p$, and let $$I_n =\{2^{ad(n)}+1, \dotsc, 2^{ad(n+1)}\}$$ as in Lemma \[l:polyintervalbinary\]. Then for every $\epsilon >0$ and $n \geq 0$, there exists a subset $A_n \subseteq I_n$ such that 1. ${{\left|M_{\varphi}\cap A_n\right|}} \geq (1-\epsilon) \cdot {{\left|A_n\right|}}$, 2. $C(A_n \mid n) \leq O[p^{n} + \log (1/\epsilon)]$, and 3. ${{\left|A_n\right|}} = \Omega(2^{ad(n)})$. In case ${\varphi}$ has the Kolmogorov property, we can replace <span style="font-variant:small-caps;">(iii)</span> with ${{\left|A_n\right|}} = \Omega({{\left|I_n\right|}})$. By Lemma \[l:polyintervalbinary\], we already know that a small fraction of programs in $I_n$ belong to $M_{\varphi}$, however we wish to obtain a much higher density of minimal indices. We whittle down the interval $I_n$ so that in the end we are left with a subset $A_n \subseteq I_n$ where at least $(1-\epsilon){{\left|A_n\right|}}$ elements belong to $M_{\varphi}$. In addition to the number $n$, our elimination process will use $O[ap^{n} + \log 1/\epsilon)]$ many bits of non-uniform advice, which will imply that $C(A_n \mid n) = O[p^{n} + \log (1/\epsilon)]$. Let us see how to obtain $A_n$ with the above properties. We let $$\begin{aligned} X &=&\text{$M_{\varphi}\cap I_n$,}\\ Y &=&\text{programs in $I_n$ that halt only on input $0$ but are not minimal, and}\\ Z &=&\text{programs in $\bigcup_{i \leq n} I_i$ that halt on input $0$ and at least one other input.}\end{aligned}$$ Note that the sizes of $X$, $Y$, and $Z$ are less than $2^m$, where $m =ad(n+1)+1$, so we can write the size of each of these sets in binary on exactly $m$ bits. Let $c \geq ap^{n} + 1$ be a function of $n$ and $\epsilon$ that will be specified later, and let $r = m-c$. Let $t(X), t(Y), t(Z)$ be the truncations of ${{\left|X\right|}}, {{\left|Y\right|}}, {{\left|Z\right|}}$ obtained by retaining the first $c$ most significants bits of the respective binary representation and filling the remaining $r$ bits with $0$'s. Since${{\left|X\right|}} \geq 2^{-ap^{n}}{{\left|I_n\right|}}$ and $c \geq ap^{n}+1$, $t(X)$ is not $0$ (on the other hand, $t(Y)$ and $t(Z)$ may be $0$). Given $n$, the values of $t(X), t(Y)$, and $t(Z)$ can be represented using $3c$ bits, and we assume that we are given this non-uniform information. Next we build in order the sets $Z', Y'$, and $X'$, which ideally should be $Z, Y$ and respectively $X$, but in fact are just approximations of these sets. <span><span>*Step 1*</span> (Construction of $Z'$):</span> We enumerate $t(Z)$ elements of $Z$, and these elements make the set $Z'$. Note that $Z' \subseteq Z$ and there are at most $2^{r+1}$ elements in $Z - Z'$. <span><span>*Step 2*</span> (Construction of $Y'$):</span> We enumerate $t(Y)$ elements $e$ of $I_n - Z'$ such that - ${\varphi}_e(0)$ halts, and - $\exists j < e, j \not \in Z'$ such that ${\varphi}_j(0) = {\varphi}_e(0)$. The enumerated elements make the set $Y'$. If $Z'$ would be exactly equal to $Z$, then $Y'$ would be a subset of $Y$. However, since $Z'$ is not necessarily $Z$, two kind of mistakes can happen. - The first kind of mistake occurs when the enumerated index $e$ belongs to $Z - Z'$. This type of mistake can happen for at most $2^{r+1}$ elements. - The second type of mistake occurs when the $j$ that witnesses the second requirement belongs to $Z - Z'$. However such a $j$ can cause at most one program $e$ to be incorrectly considered of type $Y$, when in fact it is of type $X$. Thus in $Y'$, we have: - at least $t(Y) - 2 \cdot 2^{r+1}$ programs of type $Y$, - at most $2^{r+1}$ programs of type $Z$ with the first kind of mistake, and - at most $2^{r+1}$ programs of type $X$ with the second kind of mistake. <span><span>*Step 3*</span> (Construction of $X'$):</span> We obtain the set $X'$ by enumerating the first $t(X) - 2^{r+1}$ programs that halt on input $0$ and are not in $Z'$ or in $Y'$. First note that all programs in $X$, except those that entered $Y'$ by a second type of mistake, compete in this enumeration. Therefore the enumeration will eventually collect $t(X) - 2^{r+1}$ elements. Again if $Z'$ and $Y'$ would be exactly $Z$ and respectively $Y$, then all the enumerated elements would be from $X$. Since this is not necessarily the case, two types of mistakes may happen. - The first type of mistake occurs when a program in $Z-Z'$ is enumerated into $X'$. There are at most $2^{r+1}$ such mistakes. - The second type of mistake occurs when a program in $Y - Y'$ is enumerated into $X'$. There are at most $2^{r+1}$ such mistakes. So $X'$ has $t(X) - 2^{r+1}$ elements and except for at most $2 \cdot 2^{r+1}$ many elements, all of the elements in $X'$ belong to $X$. Note that $$\frac{{{\left|I_n\right|}}}{2^m} = \frac{2^{ad(n+1)} - 2^{ad(n)}}{2^{ad(n+1)+1}} = \frac{2^{ap^{n}} - 1}{2^{ap^{n}+1}},$$ whence by Lemma \[l:polyintervalbinary\], $${{\left|X\right|}} \geq 2^{-ap^{n}} \cdot {{\left|I_n\right|}} = 2^m \cdot \frac{2^{ap^{n}}-1}{2^{ap^{n}}} \cdot \frac{1}{2^{ap^{n}+1}} \geq \frac{2^m}{2^{ap^{n}+2}}.$$ We take $A_n$ to be $X'$, so $${{\left|M_{\varphi}\cap A_n\right|}} \geq {{\left|X'\right|}} - 2 \cdot 2^{r+1} \geq t(X) - 3 \cdot 2^{r+1},$$ and therefore $$\begin{gathered} \frac{{{\left|M_{\varphi}\cap A_n\right|}}}{{{\left|A_n\right|}}} \geq 1 - \frac{2^{r+2}}{t(X) - 2^{r+1}} \geq 1 - \frac{2^{m - c+2}}{{{\left|X\right|}}}\\ \geq 1 - \frac{2^{m - c+2}}{2^{m} \cdot 2^{-(ap^{n}+2)}} = 1- \frac{1}{2^{c-ap^{n}-4}}.\end{gathered}$$ For $c= \lceil \log (1/\epsilon) \rceil + ap^{n} + 5$, the last term is greater than $1-\epsilon$. Since $A_n$ can be constructed from $n$ and the $3c$ bits that encode $t(X), t(Y), t(Z)$, it follows that $C(A_n \mid n) \leq 3 \log (1/\epsilon) + 3ap^{n} + O(1)$. Finally, $$\begin{gathered} {{\left|A_n\right|}} = t(X) - 2^{r+1} \geq ({{\left|X\right|}}-2^{r+1}) - 2^{r+1} \\ \geq 2^{m-ap^{n+1}-2} - 2^{(m-c)+2} \geq 2^m \cdot 2^{-ap^{n}-3} = \Omega(2^{ad(n)}).\end{gathered}$$ When ${\varphi}$ is a numbering with the Kolmogorov property, $p=1$ and therefore $2^{-ap^{n}}$ is a constant. In this case the last inequality implies $A_n = \Omega(2^m) = O({{\left|I_n\right|}})$. The complexity of $A_n$ above depends on $n$ but is small compared to the complexity of most large subsets of $I_n$. Indeed $I_n$ is an interval of integers of the form $\{M, \dotsc, M^{O(p)}\}$, where $M =2^{ad(n)}+1$ and the size of $A_n$ is at least $M$. The complexity of $A_n$ conditioned by $n$ is $O(\log M + \log 1/\epsilon)$, while the conditional complexity of most subsets of $I_n$ of size $M$ is $\log {M^{O(p)}\choose M} = O(M \log M)$. Furthermore, $p=1$ for numberings with Kolmogorov property, and so in this case the complexity of $A_n$ conditioned by $n$ is a linear function of $\log(1/\epsilon)$. The champion method {#s:champion} ------------------- The following lemma, used in the contrapositive form, provides a sufficient criterion for a set to avoid being $(1,k)$-recursive. While we give a direct proof in the "warm-up" of Section \[sec:wgo\], the argument below goes by contradiction. When interpreting the Champions Lemma below, it is useful to keep in mind that a $(\lfloor k/2 \rfloor +1, k)$-recursive set is already recursive @Tra55. Epstein and Levin recently discovered a related property which suffices to guarantee that sets contain elements with low Kolmogorov complexity @EL12 [@She12]. \[lem: cl-new\] Let $M$ be a set of binary strings, let $k$ and $m$ be positive integers. Suppose that $M$ is $(m,k)$-recursive. Then for all sufficiently large finite sets $A$ satisfying $$\label{eqn: dc} {{\left|M \cap A\right|}} \geq \left(1 - \frac{1}{k!(k-m+2)}\right) \cdot {{\left|A\right|}},$$ there exists $x \in M \cap A$ with $C(x) \leq C(A) + O(1)$. Let $M, m$ and $k$ be as in the hypothesis of the theorem, and let $f$ be the computable witnessing that $M$ is $(m,k)$-recursive. Assume towards a contradiction that there exists a sufficiently large finite set $A$ satisfying the density condition such that for all $x \in M \cap A$ we have $C(x) > C(A) + c$, where $c$ is a constant that will be specified later. We say that strings in $M \cap A$ are *high* and strings in $A - M$ are *low*. Let us assume that $f$ maps $k$-tuples of integers to $\{{\mathsf{H}},{\mathsf{L}}\}^k$ where the label ${\mathsf{H}}$ asserts that the string is high, and ${\mathsf{L}}$ asserts that the string is low. To obtain a contradiction, it suffices to show that $f$ mislabels at least $k-(m-1)$ positions for some vector in $A^k$. We first present a sketch of the proof. Most $k$-tuples in $A^k$ consist only of high strings, and in such vectors, $f$ must label at least one position with "${\mathsf{H}}$." Henceforth, we restrict $f$ to $A^k$. We count for each string in $A$ how many ${\mathsf{H}}$ labels it receives among all tuples, with the provision that if a string receives several ${\mathsf{H}}$ tuples in the same tuple then we count only one. Consider the lexicographically least string with the largest count of ${\mathsf{H}}$ among $k$-tuples in $A^k$. We call this string the *champion*. The champion actually has low complexity and consequently, by our assumption, is not in $M \cap A$ despite the fact that there are many $k$-tuples in which it is labeled ${\mathsf{H}}$. Let us focus on those $k$-tuples in $A^k$ where $f$ incorrectly labels the champion with ${\mathsf{H}}$. Call this set $E$, and mark in each tuple in $E$ one position where the champion is labeled ${\mathsf{H}}$. We can find many such $k$-tuples in $E$ where all the unmarked positions contain high strings. Each such vector must have at least one ${\mathsf{H}}$ label other than the marked one, as $f$ labels at least one position correctly in each $k$-tuple. We count labels the same way as before among vectors in $E$ after ignoring the marked positions. The lexicographically least string with the largest new count of ${\mathsf{H}}$ among vectors in $E$ is called the *second place champion*. Like the champion, the second place champion also has low complexity and therefore, by our assumption, is not in $M \cap A$. There are still $k$-tuples where both the champion and second-place champion receive incorrectly the label ${\mathsf{H}}$ and the remaining $k-2$ unmarked positions contain high strings. By iterating this process we obtain a $k$-tuple where $f$ mislabels each of $k - (m-1)$ positions occupied by champions with ${\mathsf{H}}$, contradicting that $f$ always gets at least $m$ labels correct. We proceed with the details. We construct sequentially some strings $x_1, x_2, ..., x_{k-(m-1)}$, the champions mentioned above, such that (a) Each of the $k-(m-1)$ champions has complexity $C(x) < C(A) + c$, for a constant $c$ that will be specified shortly, and (b) for all $1\leq \ell \leq k-(m-1)$, the number of $k$-tuples containing in $\ell$ positions the champions $x_1, \ldots, x_\ell$ labeled ${\mathsf{H}}$ is at least $[1- \ell /(k-m+2)] {{\left|A\right|}}^{k-\ell}$. This gives us the contradiction described in the proof sketch because, at stage $k - (m-1)$, it follows from (b) that there is at least one $k$-tuple containing $k-m+1$ positions occupied in some order by the champions $x_1, \ldots, x_{k-(m-1)}$ which are all labeled ${\mathsf{H}}$ even though all champions have low complexity and, consequently, taking into account our assumption, they cannot be in $M$. To start with, let us assume that we can carry out the $k-(m-1)$ iterations of the construction of champions, and let $x_1, x_2, \dotsc, x_{k-(m-1)}$ denote the champion, second place champion, and so on. Since champion $x_\ell$ can be computed when the set $A$, the index $\ell$ and the function $f$ are given, it follows that for some constant $c$ $$C(x_\ell) \leq C(A) + \log \ell + 2\log \log \ell + O(1) < C(A) + c$$ for all $\ell \leq k-(m-1)$, where the "$2\log \log \ell$" bits are used to form a delimiter for encoding the pair ${{\left\langleA, \ell\right\rangle}}$. Hence, condition (a) holds. It remains to demonstrate that all $k-(m-1)$-place champions exist, and that condition (b) is also true. We will implicitly assume that ${{\left|A\right|}}$ is sufficiently large to complete all $k-(m-1)$ stages of the construction. Let $\epsilon = 1/[k!(k-m+2)]$. By the Bernoulli Inequality, there are at least $$(1-\epsilon)^k {{\left|A\right|}}^k \geq (1-k\epsilon) {{\left|A\right|}}^k \geq \left(1 - \frac{1}{k-m+2}\right) {{\left|A\right|}}^k$$ $k$-tuples in $A^k$ consisting of only high strings, and all these tuples contain at least one ${\mathsf{H}}$ in their label. Consequently, the first champion can be chosen as stated in the proof sketch. Also, the number of tuples containing $x_1$ labeled ${\mathsf{H}}$ is at least $(1- 1/(k-m+2)){{\left|A\right|}}^{k-1}$. We shall construct $x_{\ell+1}$ by induction. Assume that $x_1, \ldots, x_\ell$ exist, and that there are at least $[1- \ell/(k-m+2)]{{\left|A\right|}}^{k -\ell}$ $k$-tuples in $A_k$ in which $x_1, \ldots, x_\ell$ appear and each receive the label ${\mathsf{H}}$. Let $E$ be the set of such $k$-tuples, and let $W$ be those vectors in $E$ for which all the non-champion positions contain high strings. Let $B$ be the complement of $W$ in $E$, that is the set of all $k$-tuples for which $f$ labels all the current champions $x_1, \ldots, x_\ell$ with ${\mathsf{H}}$ and there is at least one low string in the remaining positions. We would like to find an upper upper bound for $B$, so let us set $B'$ to be all vectors in $A^k$ that contain the current champions, regardless of how they are labeled, and at least one additional low string. Then $B$ is included in $B'$, so ${{\left|B\right|}} \leq {{\left|B'\right|}}$. Let $D$ be the set of vectors in $A^k$ which contain $x_1, \dotsc, x_\ell$ and have high strings in the remaining $(k-\ell)$ positions. Let $d$ be the number of possible ways of placing $x_1, \dotsc, x_\ell$ into a $k$-tuple. Now $d \leq {k \choose \ell} \ell!$, and equality holds if the champions are all distinct. Furthermore, $$\begin{aligned} {{\left|D\right|}} \geq d (1-\epsilon)^{k-\ell}{{\left|A\right|}}^{k-\ell} \geq [1-(k-\ell)\epsilon] d {{\left|A\right|}}^{k-\ell}\end{aligned}$$ because the current champions $x_1, \ldots, x_\ell$ are all low and thus we do not overcount when we consider different positions for the $\ell$ current champions. Now $B'$ is the set of all $k$-tuples containing $x_1, \ldots, x_\ell$ except for those in $D$, and thus $$\frac{{{\left|B'\right|}}}{d {{\left|A\right|}}^{k-\ell}} \leq 1 - [1-(k-\ell)\epsilon] = (k-\ell) \epsilon.$$ Finally, we bound the size of $W = E \setminus B$. Note that $$\begin{aligned} {{\left|E\right|}} - {{\left|B\right|}} \geq {{\left|E\right|}} - {{\left|B'\right|}} \geq \left[1 - \frac{\ell}{k-m+2} - (k-\ell) d \epsilon\right] {{\left|A\right|}}^{k-\ell},\\end{aligned}$$ and applying our estimate for $d$, we obtain $${{\left|W\right|}} \geq \left[1 - \frac{\ell}{k-m+2} - k (k-1) \dotsc (k-\ell) \epsilon \right] {{\left|A\right|}}^{k-\ell} \geq \left(1 - \frac{\ell+1}{k-m+2}\right) {{\left|A\right|}}^{k-\ell}.$$ Therefore the $\ell+1$-place champion can be chosen as described in the proof sketch, and the number of tuples containing $x_1, \ldots, x_{\ell+1}$ all labeled ${\mathsf{H}}$ is at least $[1 - (\ell+1)/(k-m+2)] {{\left|A\right|}}^{k-(\ell+1)}$. We show next that the converse fails. For every positive integer $k$, there exists a set of natural numbers $M$ that is not $(1,k)$-recursive and yet it satisfies the conditions of the Champions Lemma, i.e., for all finite sets of natural numbers $A$ at least one of the following holds true: 1. ${{\left|M \cap A\right|}} < \left(1 - \frac{1}{(k+1)!}\right) \cdot {{\left|A\right|}}$, or 2. there exists $x \in M \cap A$ such that $C(x) < C(A) + O(1)$. Let us fix $k$ and let $\epsilon = 1/(k+1)!$. We construct a set $M$ that satisfies for all integers $n$ and for all finite sets $A$ the following requirements: <span>$R_n$:</span> The $n$-th computable function $f_n$ gets all labels for M wrong on some $k$-tuple, and <span>$S_A$:</span> $A$ satisfies either <span style="font-variant:small-caps;">(i)</span> or <span style="font-variant:small-caps;">(ii)</span> above. To construct $M$ we partition ${\mathbb{N}}$ into consecutive intervals $I_0, J_0, I_1, J_1, \dotsc,\linebreak[0] I_n, J_n, \dotsc$. Each $I_n$ is an interval with exactly $k$ elements which is used to diagonalize against $f_n$ in the obvious way: $f_n$ assigns labels to the elements of $I_n$, and we define $M$ in the opposite way so that all labels are incorrect. This ensures that $M$ is not $(1,k)$-recursive. We now define the intervals $J_n$ to satisfy the requirements $S_A$. These intervals will satisfy $M \cap J_n = \emptyset$ for all $n$. More precisely, $J_n$ will witness that $S_A$ is satisfied for the finite sets $A$ where $|A| > k/(1-\epsilon)$ and $n$ is the least index such that $A \cap I_n \neq \emptyset$. We say that such sets $A$ form the *target* of $J_n$. If $t=\max I_n$, we take $J_n = \{t+1, \ldots, t+m\}$ where $m$ is large enough so that for all $A$ in the target of $J_n$, if $A$ contains an index greater than $t+m$ then $$C(A) > \max \{C(x) \colon x \in I_0 \cup \ldots \cup I_n\}.$$ On the other hand, if $A$ is in the target of $J_n$ and $\max A \leq t +m$, then $${{\left|M \cap A\right|}} \leq {{\left|I_n \cap A\right|}} \leq k < (1-\epsilon){{\left|A\right|}}.$$ Thus $S_A$ is indeed satisfied for all $A$ in the target of $J_n$. It only remains to satisfy $S_A$ for sets $A$ with ${{\left|A\right|}} \leq k/(1-\epsilon)$. This is easy because any element $x$ in such a set can be described with $C(A) + O(1)$ bits, where the $O(1)$ bits are used to represent the rank of $x$ in some canonical representation of $A$. We present the following user-friendly version of the Champions Lemma. \[thm:nonapprox\] Let $M$ be a set of binary strings. Suppose there exist a sequence of distinct finite sets $A_0, A_1, \dotsc$ and a sequence of positive reals $\epsilon_0, \epsilon_1 \dotsc$ with limit 0 such that 1. $|M \cap A_n| \geq \left(1 - \epsilon_n\right) \cdot {{\left|A_n\right|}}$, and 2. for all $x \in M \cap A_n$, $C(x) \geq C(A_n) + \log [C(A_n)]$. Then $M$ is not $(1,k)$-recursive for any $k$. Choose $\epsilon_k = 1/[k!(k+1)]$, and apply the Champions Lemma in the contrapositive form. Note that the "$O(1)$" term in the Champions Lemma depends of the constant $k$, but since $\limsup {{\left|A_n\right|}} = \infty$, we obtain for each $k$ an infinite sequence of finite sets, each with the requisite density and complexity. Non-approximability of ${\mathrm{MIN}}_{\varphi}$ {#s:minset} ================================================= We first show that the set of Kolmogorov random strings, $\{x \colon C(x) \geq {{\left|x\right|}}\}$ is not $(1,k)$-recursive for any $k$. For an arbitrary function $g$, let ${\mathrm{HIGH}}_g = \{x : C(x) \geq g({{\left|x\right|}})\}$. \[t:random\] \[thm: howfatisshe\] Let $g$ be a computable function such that both $g(n)$ and $n-g(n)$ are unbounded, and let $c$ be a nonnegative constant. Then for any positive integer $k$, 1. ${\mathrm{HIGH}}_{g}$ is not $(1,k)$-recursive, and 2. ${\mathrm{HIGH}}_{n-c}$ is not $(1,k)$-recursive. (<span style="font-variant:small-caps;">i</span>): We take $A_n$ to be set of strings of length $n$. It holds, by counting the maximum possible number of relevant descriptions, that ${{\left|{\mathrm{HIGH}}_g \cap A_n\right|}} \geq (1- 2^{-(n-g(n)-1)}){{\left|A_n\right|}}$. The complexity $C(A_n)$ is bounded by $C(n) + O(1)$, which for infinitely many $n$ is at most $g(n)/2$ because no unbounded, computable function is a lower bound for Kolomogorov complexity @LV08 [@ZL70]. Finally, for every string $x$ in ${\mathrm{HIGH}}_g \cap A_n$, we have $$C(x) \geq g(n) > g(n)/2 + \log [g(n)/2].$$ The conditions of Theorem \[thm:nonapprox\] are satisfied for $M = {\mathrm{HIGH}}_g$, and the conclusion follows. (<span style="font-variant:small-caps;">ii</span>): Since the set of $n$-bit strings not in ${\mathrm{HIGH}}_{n-c}$ do not form a vanishing fraction of all $n$-bit strings, part (<span style="font-variant:small-caps;">ii</span>) requires a more elaborate analysis. Let us focus on the case $c=0$, that is, the case of *random strings*. For positive values of $c$, the proof is similar and slightly easier. Let $I_n$ denote the set of $2^n$ binary strings of length $n$. First we argue that for infinitely many lengths $n$, at least $2^{n-2}$ strings of length $n$ are random. Indeed, if there were less than $2^{n-2}$ random strings of length $n$, then at most $(2^n - 1) - (2^n - 2^{n-2}) < 2^{n-2}$ programs of length less than $n$ could describe strings of length greater than $n$, and the number of programs of length $n$ that describe strings of length greater than $n$ is at most $2^n$. Thus at least $2^{n+1} - 2^n - 2^{n-2} > 2^{n-1}$ strings of length $2^{n+1}$ are random. Let $R$ denote the set of random strings and let $t_n$ be the number of nonrandom strings in $I_n$ encoded in binary with the last $2 \log n$ bits replaced with "$00\dotsc 0$," and let $T_n$ be the first $t_n$ elements in $I_n$ found to be nonrandom. We throw these strings out of the "arena" $I_n$, and what's left are mostly random strings. Let $A_n = I_n \setminus T_n$. Then at most $2^{2\log n + 1} = 2n^2$ in $I_n \setminus T_n$ are nonrandom. For any $\epsilon > 0$ and all sufficiently large $n$, we have $2^{n-2} - 2n^2 \geq (1-\epsilon) 2^{n-2}$, and for those infinitely many $n$ which are both sufficiently large and for which there are at least $2^{n-2}$ random strings of length $n$, we have $${{\left|R \cap A_n\right|}} \geq 2^{n-2} - 2n^2 \geq (1-\epsilon) 2^{n-2} \geq (1-\epsilon) {{\left|A_n\right|}},$$ which satisfies condition <span><span style="font-variant:small-caps;">(i)</span></span> of Theorem \[thm:nonapprox\]. Furthermore, $$C(A_n) \leq C(T_n) + O(1) \leq n - 2 \log n + O(1),$$ so we satisfy condition <span><span style="font-variant:small-caps;">(ii)</span></span> as well because every string in $A_n$ is random. The theorem follows. Regardless of which underlying universal machine is used to measure Kolmogorov complexity, Theorem \[thm: howfatisshe\] <span style="font-variant:small-caps;">(ii)</span> holds for at most finitely many negative values $c$. This follows from the fact that any string of length $n$ can described using $n+O(1)$ bits. \[t:onekrec\] For all numberings ${\varphi}$ with Kolmogorov property, for all $k$, ${\mathrm{MIN}}_{\varphi}$ is not $(1,k)$-recursive. Fix $k$, and let $\epsilon = 1/[k!(k-1)]$. Apply Lemma \[lem:pdl\] with $p=1$ (corresponding to numberings with Kolmogorov property) to obtain sets $A_0, A_1, \dotsc$ satisfying (1) ${{\left|M_{\varphi}\cap A_n\right|}} \geq (1-\epsilon) \cdot {{\left|A_n\right|}}$, (2) $C(A_n) \leq \log n + O[\log (1/\epsilon)]$, and (3) ${{\left|A_n\right|}} = \Omega(2^{\Omega(n)})$. Then ${{\left|{\mathrm{MIN}}_{\varphi}\cap A_n\right|}} \geq (1-\epsilon) \cdot {{\left|A_n\right|}}$, and by Lemma \[l:highmin\] every $x \in {\mathrm{MIN}}_{\varphi}\cap A_n$ satisfies $$C(x) \geq {{\left|x\right|}} - \log {{\left|x\right|}} = \Omega(n) \geq C(A_n) + \log [C(A_n)].$$ It follows from Theorem \[thm:nonapprox\] that ${\mathrm{MIN}}_{\varphi}$ is not $(1,k)$-recursive. The proof technique used in Theorem \[t:onekrec\] cannot be used to extend this result to acceptable numberings. The reason is that the argument in the density-boosting Lemma \[lem:pdl\] also goes through for the one-dimensional version of ${\mathrm{MIN}}_\psi$, ${\rm SD}_\psi=\{e : (\forall j <e)\: [\psi_j(0) \neq \psi_e(0)]\}$, which is known to be $(1,2)$-recursive for some acceptable numbering $\psi$ (care of the Remark following Theorem 2.3 in @ST12). By modifying the construction in @ST12 [Theorem 2.3], one can show that ${\rm SD}_\psi$ is $(1,2)$-recursive for some polynomially-bounded numbering $\psi$, which implies that the method in Theorem \[t:onekrec\] does not even extend to polynomially-bounded numberings. The necessary modification in @ST12 [Theorem 2.3] is to use intervals $J_{n,n \log^3 n}, \dotsc, J_{n,1}$ rather than $J_{n,2^{n+1}}, \dotsc, J_{n,1}$ to code the first $\log n + 3 \log \log n$ of Chaitin's $\Omega$ rather than the first $n$ bits. Then the size of the interval $I_n$ becomes less than $n^2 \log^6 n$, and hence the index $e_n$ is at most $\sum_{k=1}^n k^2 \log ^6 k = O(n^4)$. Then the numbering $\psi$ constructed becomes polynomially bounded, and the Kolmgorov complexity argument at the end still works. Non-approximability of ${{\textstyle\mathop{\mathrm{min}}}}_{\varphi}$ {#s:minf} ====================================================================== The main focus in this section is on the *shortlist for functions problem*, Question \[ques: poly-log list\], but first we consider a different type of approximation. We say that a function $f$ is *($K$-)approximable from above* if there exists a uniform sequence of ($K$-)computable functions $f_0, f_1, \dotsc$ such that for all $x$, $f_s (x) \geq f_{s+1} (x)$ and $\lim_s f_s(x) = f(x)$. We define *($K$-)approximable from below* similarly, but with the inequalities reversed. In some sense, ${{\textstyle\mathop{\mathrm{min}}}}_{\varphi}(e)$ is the function analog of Kolmogorov complexity for strings, $C(x)$. We investigate whether ${{\textstyle\mathop{\mathrm{min}}}}_{\varphi}(e)$ has approximability properties similar to those of $C(x)$. $C(x)$ is approximable from above, but not from below @LV08. For ${{\textstyle\mathop{\mathrm{min}}}}_{\varphi}(e)$, we have the following contrasting result. For any numbering ${\varphi}$, the function ${{\textstyle\mathop{\mathrm{min}}}}_{\varphi}$ is $K$-approximable from below. If ${\varphi}$ is computably bounded, then ${{\textstyle\mathop{\mathrm{min}}}}_{\varphi}$ is not $K$-approximable from above. Let ${\varphi}$ be a numbering. Using a $K$-oracle, one can enumerate all pairs ${{\left\langlee,j\right\rangle}}$ such that ${\varphi}_e \neq {\varphi}_j$ by searching for the least input on which either ${\varphi}_e$ and ${\varphi}_j$ disagree or where one function converges and the other one doesn't. Define $f_s(e)$ to be the the least index $j$ such that ${\varphi}_j(x) = {\varphi}_e(x)$ for all $x \leq s$. Now $f_s(e)$ is an increasing function which eventually settles on ${{\textstyle\mathop{\mathrm{min}}}}_{\varphi}(e)$, and therefore $f_0, f_1, \dotsc$ is a uniform, $K$-computable sequence of functions witnessing that ${{\textstyle\mathop{\mathrm{min}}}}_{\varphi}$ is $K$-approximable from below. If ${\varphi}$ were computably bounded and also approximable from above, this would imply that ${{\textstyle\mathop{\mathrm{min}}}}_{\varphi}$ is a $K$-computable function, whence ${\mathrm{MIN}}_{\varphi}\leq \emptyset'$, contradicting Lemma \[lem: nolala\]. Although we can approximate ${{\textstyle\mathop{\mathrm{min}}}}_{\varphi}$ from below using a halting set oracle, no unbounded computable function bounds ${{\textstyle\mathop{\mathrm{min}}}}_{\varphi}$ from below when ${\varphi}$ is computably bounded. In this sense, ${{\textstyle\mathop{\mathrm{min}}}}_{\varphi}$ resembles Kolmogorov complexity $C(x)$ @LV08 [@ZL70]. For every computably bounded numbering ${\varphi}$, there exists no unbounded computable function $h$ such that ${{\textstyle\mathop{\mathrm{min}}}}_{\varphi}(e) \geq h(e)$ for all $e$. Suppose that for some computable, unbounded $h$, ${{\textstyle\mathop{\mathrm{min}}}}_{\varphi}(e) \geq h(e)$, for all $e$. Let $U$ be the underlying universal machine for the Kolmogorov complexity function $C$. Define a numbering $\psi$ by $$\psi_q = {\varphi}_{U(q)},$$ and let $t$ be a "translator" program such that ${\varphi}_{t(q)} = \psi_{q}$ and $s$ a computable function such that $t(q) \leq s(q)$ for all $q$. Let $s'$ be the unbounded computable function defined as follows: $s'(x)$ is the smallest $y$ such that $s(y) \geq x$. Let $e$ be an arbitrary index, and let $p$ be a shortest program such that $U(p)=e$. Thus ${{\left|p\right|}} = C(e)$ and therefore $p < 2^{C(e)}$. Note that ${\varphi}_{t(p)} = \psi_p = {\varphi}_{U(p)} = {\varphi}_e$ and consequently $t(p) \geq {{\textstyle\mathop{\mathrm{min}}}}_{\varphi}(e) \geq h(e)$. Hence, $s(p) \geq h(e)$ and thus $s(2^{C(e)}) \geq h(e)$. It follows that $C(e) \geq \log (s'[h(e)])$ for all $e$. Thus $C(e)$ is lower-bounded by a computable, unbounded function, which is impossible @LV08 [@ZL70]. We now turn our attention to the *shortlist for functions problem*. The next theorem and proposition show that in the general case of acceptable numberings, only a weak lower bound on the length of shortlists is possible. \[thm:listlength2\] For any
{'source': 'arXiv_out/1409'}