6
$\begingroup$

Let us say a set $X$ satisfies Property A if$$\liminf_{n \to \infty} {{\left|X^{\le n}\right|}\over n} = 0.$$Are there recursive sets $X$ satisfying Property A that contain infinitely many incompressible strings?

$\endgroup$
4
  • 1
    $\begingroup$ Can't you just add another such string, and then wait a long time, adding nothing, so that the density comes down very low, before adding the next one, of correspondingly long length? (And could you clarify whether you intend that $X$ is a set of strings, or a set of numbers from which strings are drawn? And does $X^{\leq n}$ means the subset of $X$ of strings of length at most $n$?) $\endgroup$ Jan 5, 2017 at 16:09
  • $\begingroup$ In fact, that idea will make $X$ have density zero, with lim=0 instead of merely liminf. $\endgroup$ Jan 5, 2017 at 16:26
  • $\begingroup$ @JoelDavidHamkins Your suggestion seems to require being able to tell when a string is incompressible, but as far as I know, incompressibility is only co-r.e. $\endgroup$ Jan 5, 2017 at 17:09
  • $\begingroup$ You are right, and that prevents limit=0, but the idea still works for liminf by adding all strings of length n for a sufficiently sparse set of n. $\endgroup$ Jan 5, 2017 at 17:38

2 Answers 2

5
$\begingroup$

I assume that $X$ is a set of binary strings and the binary strings are coded by natural numbers in this way: consider this enumeration of all strings:

$\lambda$, 0,1,00,01,10,11,000,.....

(in which, at first we have the string with length zero, then all strings of length one in alphabetical orde and so on).Now code the $n$ th member of this enumeration by the number $n$.

Now we define the set $X$ as $\{w~:~ |w|=2^i~ for ~some ~i\in \mathbb{N}\}$ ($|w|$ denotes the length of the string $w$).

It can easily checked that $X$ satisfies the property $\textsf{A}$. It is also well-known that we have incompressible strings of any length (because the number of Turing machines of length<$n$ is at most $2^n-1$ but we have $2^n$ string of length $n$). Therefore $X$ contains infinitely many incompressible strings.

$\endgroup$
3
$\begingroup$

I'm assuming you call `incompressible' integers whose binary representation $x$ satisfy $K(x)>|x|-c$ for a fixed $c$?

If that's the case, the answer is no. If $X$ is a computable set of integers and some integer $k$ of representation $x$, with $|x|=N$, belongs to $X$, then $K(x|N) \leq \log |X^{\leq 2^{N+1}}| + c'$ for a fixed $c'$. (Indeed one can describe $x$ by just giving its position as a string of length $N$ inside $X$). But by your assumption on $X$, $\log |X^{\leq 2^{N+1}}| - N$ tends to $-\infty$, so almost all strings in $X$ satisfy, say, $K(x\mid|x|) < |x| - 3c$. You can then remove the the condition $|x|$ and get $K(x) < |x| - 2c$ by a usual padding technique (see the book by Li and Vitanyi, I can elaborate if this is important).

$\endgroup$
3
  • $\begingroup$ He only has liminf, not lim, and so unless I am mistaken, your remarks about "almost all" and "tends to" seem inaccurate. $\endgroup$ Jan 5, 2017 at 19:59
  • $\begingroup$ ha indeed I read limit! So ok, as Joel says, if you only require liminf =0, the answer is obviously yes by putting in your set all strings of length N for all N in a sparse set of integers. With lim = 0 the answer is no as per my explanation. $\endgroup$ Jan 5, 2017 at 21:58
  • 1
    $\begingroup$ I would venture to guess that the question "should" have specified lim rather than liminf, though of course only Andrew S. can say for sure. $\endgroup$ Jan 6, 2017 at 2:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.