信息熵的基本意义是反映消息最少需要的平均编码长度。

计算理论主要是研究是计算复杂性的理论，计算复杂性一般主要指计算时需要的时间和空间复杂性，特别是时间复杂性。

信息论与计算理论有一个小小的桥梁，就是Kolmogorov复杂度。Kolmogorov复杂度描述的是一段计算机程序最少需要的编码长度。一般而言产生一条消息（注意是产生，而不是求解）的计算机程序的Kolmogorov复杂度与这条消息的最小编码长度近似。

根据信息论，一般而言消息是可以压缩的（这里专指无损压缩）。在通信中经常采用压缩技术来减少通信开销。压缩和解压缩程序本质上都是图灵机。因为压缩与解压缩都是无损的，所以压缩和解压缩并不改变消息的任何信息含量。从解压缩方来看，将压缩数据经过解压程序运算就得到了想要的数据。

现在考虑这么一个信息传递问题：

Alice要向Bob发送所有10位数以内的所有素数。她有三种选择：

     1. 是直接将所有这些素数传送给Bob；

     2. 将这些素数压缩（ZIP?）后和解压程序一起传送给Bob;

     3. 发送一个求解10位数以内所有素数的程序给Bob，Bob收到程序后，运行程序就可以得到这些素数了;

无论选择哪种方法，Bob都可以得到10位数以内的所有素数。问题是这三种方法是否等价？

从Bob最后要得到的结果来看，三者无疑是等价的（如果Bob对时间一点都不在乎）。

从信息论的角度来看，1和2等价是没有什么问题的，压缩与解压不过是对信息的不同编码方式进行转换，不会改变信息的任何内容。但是3呢？从信息论的角度来看，3和1，2应该是不同的。因为Alice发送的消息与Bob需要的消息是完全不同的东西，用信息熵来度量的话，Alice发送的程序的最小编码长度（或者Kolmogorov复杂度？）可能远小于这些素数的最小编码长度（但是Bob却还是能得到他需要的素数）。

如果考虑额外的计算开销。3的方法给Bob带来了额外的开销，3不能和1等价，但是方法2同样也给Bob带来了额外的运算开销。解压缩程序与计算素数的程序都是图灵机，并无本质上的不同。所以如果考虑额外的计算开销，2与1也就不等价了。

另外一个场景：

Alice向Bob传送联通北京所有景点的哈密顿回路（货郎担问题）。Alice有3种选择：

1. 将哈密度回路直接发给Bob(可以压缩也可以不压缩，这里看做等效的)

2. 将北京景点图发给Bob，让Bob自己去找

3. 将北京景点图和计算哈密顿环路的程序发给Bob

1，2，3是否等效的问题这里就不讨论了，这里讨论其他两个问题。

首先第一个问题，景点地图所包括的信息是不是包含了该图的哈密顿环路的信息？ 首先从信息论的观点出发，信息一旦损失，就不可再恢复。消息进行有损压缩后，如果不补充新的知识，无论用什么解压算法，都不可能还原。但是根据图，是一定可以找到哈密尔顿回路的（如果不考虑时间限制的话）。另一方面，直观上来讲，仅从一张图尔得到该图的哈密尔顿回路却是很困难的。

第二个问题，如果给了图和计算程序（情况3），是不是就可以讲图和程序共同包含了哈密尔顿环路的信息？ 但是有可能Bob的假期都过了，他还没能得到他要的回路。

从上面的的问题可以看出，信息论无法统一度量信息传递过程中的所有开销。压缩方法以增加计算开销的方式来获得较小的传输开销。但是按照信息论，传输开销的减小程度是有限制的。但是根据方法3的情况，有可能通过增加计算开销来将传输开销降低到信息熵的限制以下。根据这些事实，是不是可以猜想，信息与计算是遵循一定规律转化的？更进一步，对于一个传输过程，信息与计算之和是不是守恒的？

转载本文请联系原作者获取授权，同时请注明本文来自张夏天科学网博客。
链接地址：https://blog.sciencenet.cn/blog-230547-224850.html


下一篇：Ubuntu安装显卡驱动