程序的信息量以及反向运行

最后更新日期:2014-06-12

1. 数据的两种形态:离散态和序列化态

2. 我看待程序的一个观点:信息流

程序 = 输入 + 中间数据处理 + 输出

输入 = 序列化态 -> 离散态 = 反序列化

  1. 手工 split
  2. 正则表达式
  3. parser

输出 = 离散态 -> 序列化态 = 序列化

  1. 手工字符串拼接
  2. 模板

中间处理 = 离散态 -> 离散态

3. 信息流三定理

定理3.1(信息流第一定理):在计算机系统内,信息不能凭空产生,只能从一种形式转换成另一种形式。

例 3.1.1:随机数是否凭空产生信息?

  1. 一般的伪随机数生成器(Pseudo Random Generator)只根据种子和确定的算法生成,信息全部从种子来
  2. 真随机数(如 /dev/random)使用硬件收集环境噪音,信息从环境中来

定理3.2(信息流第二定理):信息只能沿着信息量不变或减少的方向流动。

定理3.3(信息流第三定理):自由意志(free will)可以凭空创造信息。

4. 信息量与热力学第二定理

定理4.1:同一份数据的离散态的信息量大于或等于其序列化态。

5. 程序的反向运行

程序的输入和输出互为反操作:

问题5.1:输入和输出可以使用同一个模板吗?(或:将输入处理程序反向运行,能否进行输出处理)

问题5.1.1:Mustache 模板能反向运行吗?

或:如何从一个 Mustache 模板生成的字符串和模板,得到 json?这是可以做到的吗?

由于序列化态的信息量比离散态低,增加的这部分信息从那里来?

如果不行,那么需要满足什么条件才可以?或者能否重新设计一套模板系统使得它可以反向运行?

6. prolog: 可以反向运行的编程语言

例6.1:prolog 的列表连接函数:append(X, Y, Z)

正向运行:

反向运行:

P.S. 据说用 prolog 写 parser 就可以实现类似我前面说的反向模板,很想学一下。

7. 写一个信息量不变的程序

定义7.1:自产生程序:自己输出自己的源代码的程序。

要求:

  1. 不能读文件(信息从文件来)
  2. 不能用编程语言提供的反射机制(信息从编程语言运行时来)

例:js 的 function 的 toString() 直接得到源代码属于 cheating

P.S. 我在这篇文章中阐明了为什么自产生程序一定要设置一套鉴定 cheating 的规则。