有趣的睡前说：图灵机、幺半群、范畴，其它

先来个表格：

假如一个群还满足交换律，那么就是阿贝尔群，不然就是非阿贝尔群。比如平移是阿贝尔群，但平移和旋转结合在一起则构成了非阿贝尔群。

如果一个群可以表征某个微分流形，那么这个群就是李群，而那个微分流形就是这个李群的齐性流形。

李群在无穷小邻域上的行为，可以由李代数描述。

当然所有这些和今天想要说的话题，都没啥关系。

除了最开始的那张表。

什么是图灵机？

我们用最抽象的语言来描述的话，大概就是这么一种东西：

将特定的输入转换为特定的输出的一种数学对象，就可以看作是图灵机。

当然了，这个说法肯定是抽象得抽过头了。

比较原教旨的说法，图灵机是一个七元数学对象，具体大家可以自己去查。但从比较本质的角度来说，图灵机所作的，就是通过不断改变自己内部状态，将输入态转换为输出态的一个数学对象。

有一类东西是和图灵机非常接近的，比如RealMachine——不是“真实的机器”，而是“实数机”。

RM和TM的区别在于，TM的输入、输出以及内部状态，都是离散的，而RM允许连续的参量。

现在，让我们来看这么一个集合：所有图灵机构成的集合T。

除了T，我们再定义一个集合，就是所有字符串构成的集合S。

但，我们知道，很多时候T中的两个图灵机t1和t2可能是“全同”的，即对于S中任意字符串s，t1(s)=t2(s)，或者s同时无法让t1和t2接受，那么就说t1和t2相等。

利用相等关系可以构造T上的等价类，然后幂掉这个相等关系，就可以得到一个更加“纯粹”的图灵机的集合，我们依然记为T。

然后，我们知道，任意图灵机t都可以在S中选取部分字符串集s(t)，作为t可接受的字符串，s(t)中的任意字符串都可以作为t的可接受输入，然后图灵机会在有限时间内停机，并给出恰当的输出。

因此，任意图灵机t都是S上的偏函数，将S的子集变换为S的另一个子集。

当然，我们可以做另一种分析——假定不可接受字符串的输出结果我们强行定义为某个特定的字符串，而同时如果接受了却不永不停机，我们也认为这等于是输出了一个无限长字符串，那么进行这样的“补完”后，任意图灵机t都可以认为能将S这个整体映射为S的某个特定的子集。

接着，如果t1和t2都是图灵机，那么t1.t2可以看作是一个将输入经过t1转换为中间态字符串，然后将这个中间态字符串作为t2的输入并最终得到输出，这么一种“联合”图灵机。

在定义了这种“联合”操作“.”后，我们可以发现，联合操作是满足结合律的——在“补完”的视角下，这点毫无疑问；而在非“补完”的情况下，这对t1的可接受输入集存在一个源自t2的额外要求，但t1.t2这个东西作为图灵机依然是存在的，所以依然是T的元素。

因此，我们说，至少是满足结合律的。而根据定义，T既然是所有图灵机的集合，那么自然是封闭的了。

再接下来，幺元当然是存在的：图灵机O就是将输入原封不动地输出的图灵机，而且这样的图灵机可以有不止一个——但它们彼此肯定等价，所以视为唯一的一个（按照上面模掉等价类的方法）。

这样的图灵机O在联合操作“.”下，可以保证无论左联合还是右联合，被联合的图灵机与联合后的图灵机的效果是一模一样的。

因此，存在幺元。

那么，是否存在逆元呢？

由于图灵机可以存在这么一种：将任何输入都输出到固定的字符串s上，从而我们不可能通过s“逆向”分析出输入字符串是什么，因此这就表示并不是任何图灵机都有逆元的。

经上所述，我们发现，符合结合律，有幺元，无逆元，满足封闭性，从而是幺半群。

这里，更好的描述方法恐怕是结合这篇文章中提出的等价网的模型了。

也就是说，在等价网上，节点之间的连线构成半范畴——图灵覆盖的特殊性导致了幺元可能不在图灵覆盖中，封闭性更是在某些覆盖下无法保证，从而连线本身构成半范畴。

那么，如果是RM而非TM，我们得到的是什么？

原本在TM中是离散的点阵构成的全序网，而现在则是连续流形上的全序网——即经过这个连续流形上任一点的任意“指向未来”的曲线都无法再回到这个点，即不存在“类时闭曲线”。

当然这个说法是非常“类比”的，

然后，回到那个古老的问题上来：

假定是一个半范畴，那么如果a不能写成b+c的形式，则说a是纯的，求A中纯元素的分布。

回到前面的等价网上，可以看到这个问题在等价网上的回答是很显然的：所有Root节点就是所有纯元素。

好了，问题到了最后一个环节。

如果我们将上述等价网中的图灵覆盖的选择，视为一个“理论系统”，我们是否有什么手段可以评判这个理论系统的某些优劣等性质？

比如说，有的理论可能Root节点很多，有的理论可能图灵覆盖的元素很多从而连线很多，那么是否有什么方法可以做出恰当的评判呢？

在等价网的例子中，图的“总影响力”，即每个节点s的Local(s)的总和，作为一张图的总影响力，那么这个值或许的确可以作为一个评判标准。

但只用一个值来判断，恐怕还是太少了点，会丢掉很多细节。

那么是否可以存在更多的评判标准呢？

尤其，当我们考虑某个实际的理论体系的时候，这个值随着时间的演变，随着理论体系的演变，会如何发生变化呢？

这的确是一个很有趣的话题啊~

来源：https://www.jianshu.com/p/2a539334eafa

著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。