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?
$\begingroup$
$\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$– Joel David HamkinsCommented 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$– Joel David HamkinsCommented 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$– Andreas BlassCommented 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$– Joel David HamkinsCommented Jan 5, 2017 at 17:38
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
3
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).
-
$\begingroup$ He only has liminf, not lim, and so unless I am mistaken, your remarks about "almost all" and "tends to" seem inaccurate. $\endgroup$ Commented 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$ Commented 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$ Commented Jan 6, 2017 at 2:39