这是一个理论问题,所以期望这里的许多细节在实践中甚至在理论上都是不可计算的.
假设我有一个s我要压缩的字符串.结果应该是一个自解压二进制文件(可以是x86汇编程序,但它也可以是其他一些假设的图灵完全低级语言)输出s.
现在,我们可以轻松地遍历所有可能的二进制文件和程序,按大小排序.让我们B_s输出这些二进制文件的子列表s(当然B_s是不可计算的).
由于每一个正整数的集合必须有一个最低限度,必须有一个最小的程序b_min_s在B_s.
对于什么语言(即字符串集)我们知道的大小b_min_s？也许只是估计.(我可以构建一些简单的例子,我可以随时计算,但我B_s也b_min_s对更有趣的语言感兴趣.)
Mat*_*hen 16
这是Kolmogorov的复杂性,你是正确的,它是不可计算的.如果是,你可以创建一个长度为n的矛盾程序,打印出一个字符串,其中Kolmogorov复杂度为m> n.
显然,你可以b_min_s接受给定的输入.但是,据我所知,大多数这样做的努力都是存在证据.例如,正在进行压缩英语维基百科的竞争.
克劳德·香农(Claude Shannon)在他1951年的论文"印刷英语预测和熵"(PDF,1.6 MB.Bell Sys.Tech.J(3)p.50-64)中估计英语的信息密度在每个字符0.6到1.3位之间. ).
| 归档时间： |
|
| 查看次数： |
10269 次 |
| 最近记录： |