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

先来个表格:

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

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

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

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

除了最开始的那张表。

什么是图灵机?

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

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

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

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

有一类东西是和图灵机非常接近的,比如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

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180628A1O3B900?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券