这篇笔记紧跟着上一篇。
在这篇记录中，所谓随机字符串被这么定义：
如果字符串只能被直接将其打印出这一种图灵机所输出，而不能成为别的任何比这图灵机更精简的别的图灵机的输出，那么这个字符串就称为是随机的。
这个表达继承自这么一个思路：随机字符串不能成为任何函数的结果。
而这个表达本身又关联到AIT[1]的一个有趣的理论：K氏复杂度，或者说描述复杂度，或者说算法熵。
一个字符串s的K氏复杂度可以这么表示：
K(s)=min(len(t), t属于T_s)
其中T_s表示所有输出结果为s的图灵机构成的集合，t是T_s的元素，len(t)表示t在通用图灵机中作为输入的字符串长度。
因此，s的K氏复杂度是所有可以输出s的图灵机中最“短”的图灵机的字符量。
由此引申出的两个概念就是：
- 如果K(s)>len(s)，那么s就是随机的；
- 如果K(s)<len(s)，那么s可以被压缩。
也就是说，随机字符串是不可压缩的——废话。
当然，我们可以做一个小小的改变——假定P(s)是所有直接打印s的图灵机中字符量最少的那个图灵机的字符量，于是上面的结论可以修改为：
- 如果K(s)>P(s)，那么s就是随机的；
- 如果K(s)<P(s)，那么s可以被压缩。
当然，这么改进并不会从本质上改变什么，只不过在s本身足够简短的时候让上面的结果更有效一点罢了（但是我们却担负上了什么是“直接打印”的定义疑难）。
到这里一切都看上去蛮正常的。
但，有一个问题最近却冒了上来——
假定t是输出s的所有图灵机中最“短”的那个，同时在通用图灵机U看来，t本身也是字符串（万物皆数据，万物皆函数，万物皆图灵机，lambda教万岁～～）。
现在有一个问题：t输出s，那么s的信息是不是都蕴含在t中呢？
这里我们假定t不接受任何输入——即便接受输入，比如t(x)=s，那么我们可以构造t'=()->t(x)来作为这里的t，只不过“微调”了最“短”这个要求的定义而已——那么也就是说，通过t获得s的过程完全不借助外界，外界信息流入为0，从而流出的信息，也就是s所蕴含的信息，必然全部来源于图灵机t。
从而，图灵机t与字符串s必然拥有相同的信息量。
而，在U看来，t是否可压缩？如果t可压缩，那么和最短要求矛盾。
因此，t是不可压缩的，从而按照K氏复杂度的定义，不可压缩的就是随机的，从而具有极高算法熵——那么问题来了，t和s具有相同信息量，s可压缩，从而不是随机de；t不可压缩，从而是随机的。
那么，这就是说，随机与否和是否含有信息没关系，这里随机与否仅仅与是否可压缩有关。
可，这样的“随机”真的够“随机”么？
举例来说，一副800px × 600px的风景画，每个像素上都是rgb256色值，完全不做压缩就以这个800 × 600 × 8 × 8 × 8 = 2.4576亿个字节地写下来，那么这幅画的信息量当然是很大的。然后，这幅风景画通过无损压缩成为PNG文件，这个PNG文件与原来的风景画含有完全相同的信息，但这个PNG文件已经几乎不可能再被进一步压缩了。
因此，这就是说，可压缩的字符串（2.4576亿字节）与不可压缩的字符串（PNG）具有（几乎）相同的信息量，但在可压缩性上两者完全不同。
因此，如果说随机表示无信息或者信息量很低，那么显然在上面的例子中，不可压缩的字符串与可压缩的字符串具有几乎相同的信息量，从而使得是否可压缩与是否含有较高信息、是否随机没有了完全必然的联系。
进一步，事实上K氏复杂度本身有表示了算法上，我们发现在上述例子中，原始字符串与压缩后的字符串很可能共享了相同的K氏复杂度，而这也就是说这两个字符串具有相同的算法熵。
算法熵相同，那么信息量应该也可以理解为相同——从这个角度来说，是否可压缩完全不影响信息含量。
换言之，如果<u>随机只是被理解为不可压缩，从而表示“不能由直接打印字符串本身以外的任何方法来获得”</u>，那么这样的随机与熵的高低以及信息含量的多少没有关系。
但，反过来，如果将随机理解为熵极大的状态，从而信息量尽可能地小，这样的随机字符串是否依然可压缩呢？
这个问题倒是还没有想明白。
如果说熵极大随机不可压缩，那么也就是说熵极大随机自然就包含在了不可压缩随机之中，从而熵极大随机自然也是“不能由直接打印字符串本身以外的任何方法来获得”的。
而如果熵极大随机可压缩，这就好玩了，它表示可以通过某些图灵机来生成熵极大随机的字符串，极端情况下，就是说，可以通过某些函数来生成熵极大的随机字符串——这点本身似乎是难以想象的。
所以，个人这里倾向于认为熵极大的随机是不可压缩的。
而这就表示了这么一种情况：
一个字符串可以被分解为这么两部分：可以被压缩而去掉的“冗余”部分，以及不可被去掉的“信息”部分。
K氏复杂度实际上给出的是不可被压缩去除的信息所对应的算法熵。
Kolmogorov与Martin-Lof关于随机的理念包括这么两条[2]：
- 不可预测：如果知道随机序列的前n项，无法推测出第n+1项；
- 不可压缩。
下面，我们来看一个问题：
数列0, 1, 2, 3, 4, 5, 6, 7, 8......
这样的序列当然是有规律的不随机的，然后假定可以生成这货的最短函数为：f(i)->i。
这样，该数列q的K氏复杂度也就是f的K氏复杂度，为7，且f不可进一步压缩。
那么，我如果直接给你f(i)->i，它到底是否随机呢？是否可预测呢？是否有信息呢？
信息方面，显然是有的，而要说随机，这货明显是一个函数啊。。。
可预测性这个问题就比较微妙了，或许我们可以看下面这个问题：
如果你已经知道了
f(i)->，你是否可能知道下一位是i？
这个问题就很微妙了——如果你已经知道原始数列是0, 1, 2, 3, 4, 5, 6, 7, 8......，那么你自然可以推断出下一位是i。但要知道这个的前提是你必须知道一组原始信息。
也就是说，现在我们面对的是这么一个情况：
- 如果不知道一组原始数据，那么我们其实很难知道
f(i)->的下一位是什么
下一位可以是
i，也可以是1，也可以是i+1，或者2*i，或者exp(i,2)，都有可能
- 如果知道原始数据，那么我们应该可以有较大地把握知道下一位是什么，但此时需要额外输入——原始数据。
如果让我们反过来，我们已经知道0, 1, 2, 3, 4, 5, 6, 7, 8这前九位值，是否可以合理地推断出下一位呢？我们同样有和上面一样的两个情况：
- 如果不知道正确的生成这个字符串的函数，那么我们较难确定下一位到底是多少；
比如说，生成这个字符串前九位的函数可能是
f(i)->i，那么下一位就是9；也可能是f(i)->floor(1.12*i)，那么下一位就是10；还可能是f(i)->i-floor(0.12*i)，那么下一位就是8。因此知道前九位并不能唯一确定第十位。
- 如果知道正确的生成这个字符串的函数，那么我们可以准确知道下一位是多少。
如果将原始序列记为D，其前n位记为D(n)，第n位记为D_n，对应的生成D的图灵机记为T，其前n位字符串记为T(n)，第n位记为T_n，那么上面的关系实际上就是：
- 不知道T，那么通过D(n)我们<u>无法知道</u>唯一的D_{n+1}
- 不知道D，那么通过T(n)我们<u>无法知道</u>唯一的T_{n+1}
- 知道T，通过D(n)<u>完全可以</u>确定D_{n+1}
- 知道D，通过T(n)<u>应该可以</u>确定T_{n+1}
我们发现这里的情况呈现出一种不对称性。
在前两组（不知道T和D）中，实际上不能确定的“程度”或者说确定的“难度”也是不同的，在不知道T的情况下从D(n)推断D_{n+1}，随着n的增大，可选择的预测范围是可以缩小的；而在对偶的情况下，不知道D要从T(n)推断T_{n+1}则是完全没有可能。
在后两组（知道T和D）中，这种不对称就更加明显了。
如果我们将从D(n)推断D_{n+1}的难易程度成为D的可预测性，从T(n)推断T_{n+1}的难易程度成为T的可预测性，那么上述不对称性其实就是说：无论知不知道D和T，D的可预测性都好于T。
事实上第四种情况与第一种情况还存在一组联系，因为要做到第一条，我们实际上就是要先做到一个受限版本的第四条，而且随着n的增加，这个限制也在减弱。
而，第二与第三条则无法构成这种联系。
在上一小节中的图像压缩的例子中，我们假定现在D是原始字符串，T是D经过压缩算法获得压缩字符串，那么上述不对称性恐怕就会被打破：
如果知道T，我们当然可以从D(n)推断出D_{n+1}；反之，如果知道D我们自然也可以通过T(n)推断出T_{n+1}。而，反过来，如果不知道T或者D，我们也就无法通过D(n)或T(n)来获知D_{n+1}或T_{n+1}了。
这里两者完全对称——也就是说此时D和T的可预测性相当。
从这两个例子，我们或许可以得到这样的结论：
D压缩后的字符串可以分解为两部分，一部分是包含了构造D的算法的，记为P；另一部分则包含了通过P构造出D的核心数据，记为K。
从而，P的可预测性比D更弱，而K的可预测性与D相当。
现在，我们可以将数据D分解为三部分：
- D的可压缩部分R；
- D的生成算法部分P；
- D的核心数据部分K。
其中，R可以被压缩掉，P和K不可被压缩，P的可预测性弱于D，K的可预测性与K相当。
在论文《Logical Depth and Physical Complexity》中，就给出了与这里相同的结论，其中K便是字符串的逻辑深度，并被引申到了物理系统的复杂性这一跨界问题上。
好了，今天睡前要记的笔记就记到这里，欧耶～～～
