我将根据Kolmogorov 复杂度来回答这个问题，它是给定固定描述语言的有限序列的最小描述的长度。如果 Kolmogorov 复杂度至少与序列的长度一样大（即序列不可压缩），则序列称为 Kolmogorov 随机序列。

对于您的问题，我们使用固定通用图灵机上的程序集作为描述语言。不失一般性，我们可以假设通用图灵机使用二进制字母表。对于每个自然数$n>0$, 存在一个 Kolmogorov 随机序列。证明很简单：有$2^n$长度序列$n$， 但只有$2^{n-1}$长度小于$n$. 所以根据鸽巢原理，肯定有一些序列——事实上，至少$2^n - 2^{n-1} = 2^{n-1}$序列——长度$n$是不可压缩的。

这个证明当然不是建设性的。此外，如果给定序列是 Kolmogorov 随机序列，则它是不可计算的。

更新

与统计冗余建立联系：如果您通过某个随机过程生成序列，则 Kolmogorov 复杂度除以序列长度会收敛到生成过程的熵（随着序列长度趋于无穷大）。因此，由伯努利过程生成的 p=0.5 的序列将是“Kolmogorov random in the limit”。

我将很快改进我的上述评论：如果压缩算法是固定的，那么只需通过迭代算法就可以获得任意大的不可压缩（使用此算法）数据。如果在达到所需大小之前出现了一个循环，请从该循环中选择一个起点，然后重试。

$\def\N\{\mathbb N^*}$详细信息。考虑到数据是 0 和 1 的字符串，一个文件（在以 1 为前缀之后）只不过是一个（非零）整数。文件的长度是。到的单射函数（它必须是单射的以确保解压缩是可能的）。我们说是不可压缩的。$n\in \N*$$\log(n)$$\N$$\N$$n$$\log(n) < \log(f(n))$

我将区分两种情况（不是绝对必要，第一种情况更好）首先，假设是非满射的，并且您知道一些（这对于实际示例来说是非常合理的）。由于是单射的，如果轨道最终是循环的，它必须再次经过。作为 ，这是不可能的：所以轨道最终不是循环的，它必须经过任意大数。更准确地说，连续数字的长度不时增加两次，因此这个序列包含无限数量的不可压缩数字。有些必须大于规定的尺寸。$f$$n \notin f(\N)$$f$$f^{(k)}(n)$$n$$n \notin f(\N)$

在一般情况下，选择一个数字并迭代。之前遇到了所需大小的不可压缩数，那么您就完成了。在另一种情况下，从循环中选择一个起点，然后重试。你迭代这个，每次都排除前面描述的所有循环。生成的序列还包含无限数量的不可压缩数字。$n$$n$