Automata

这段时间都在和各式各样的自动机打交道，甚至晚上睡觉都想抱住我最喜欢的下推自动机。总之就是学得非常开心，毕竟计算理论是一个我初次接触就被深深吸引的领域——还是在一年前的一阶逻辑课程上，一位数院学长给我们讲述可计算性的基本概念、Church-Turing Thesis，讲述如何将P/NP问题归约为逻辑问题以期解决。"可计算性"这样一个无比模糊的直观概念竟能得到精确的数学刻画并发展成一整个严肃的学科本身就很令人惊异了，从不同角度观察“计算”这件事情的人们曾抽象出许多模型：递归函数、-演算、图灵机、正规算法……而这些表面看起来截然不同的刻画最后都被证明是等价的，使人们更有理由进一步宣称：它们所刻画的可计算性概念就是我们所需要的可计算性概念。

当下我就有种遇到了想要抓住的东西的心情，将其列为一定要深入学习的事项之一。也找了本书来看，不过我当时资历尚浅，那本复旦的递归论教材可读性又极低¹，并没能看下去。这学期万事俱备，可以好好学习一番了，于是选了一门计算理论，一门程序理论的课程，又在编译原理课程上偶然再次邂逅了它。仅仅是NFA（非确定型有穷自动机）与DFA（确定型有穷自动机）的等价性证明就在三门课上学了三遍，应该是刻进DNA这辈子不会忘记了。

虽是学了三遍，却不代表是在重复完全一样的内容，同样的事物我们从不同的角度去刻画就可能得到崭新而有趣的结论——这也是我最近一个很深的体会。上次有这样的体会，是在学习Fraisse Theorem的时候。对于两个数学结构，要试着去刻画它们之间的关系，首先能想到的是代数刻画，就像我们在抽象代数课程上所做的那样，在两个结构之前建立态射，对其加以限制得到各种强度的同态关系。这是一种将结构“剥开”的方法，因为我们要去观察结构上的各种函数与关系的行为与特征；除此之外我们还可以进行逻辑刻画，完全不考虑这些结构本身是什么样的，而去比较对它们而言为真的逻辑公式集的范围；更进一步地，还可以采用博弈论刻画，即构造一种特殊的博弈，用这种博弈的必胜策略来模拟结构的关系。最后我们要回过头来考察不同刻画方法之间的关系，Fraisse Theorem所做的正是这样一件事，它在有穷同构、初等等价和E-F博弈三者之间建立了关系。

而在计算理论的学习中，这种体会就更深了。对于某种强度的计算能力，我们可以直接去构造抽象机，描述这些机器的装置与行为，也就是去关注计算的每一个步骤；我们同样可以不考虑计算究竟是如何进行的，而去描述机器可识别的语言集合；对这些语言，又可以去问它们有怎样的语法结构，能生成它们的文法规则是怎样的。从不同角度出发、甚至根本就是不同领域的研究者又往往会合于一处：语言学上划分的四型语言恰好对应四个典型的计算强度，为编译器而生的Backus-Naur范式、语言学的乔姆斯基范式、下推自动机这种抽象机三者是等价的。上学期听王彦晶老师讲做模态逻辑的人和做CS的人从完全不同的问题需求出发都得到了互模拟这个概念，大约也是如此。

对“计算”从不同角度进行的考察，不仅影响上面提到过的各种抽象模型，还影响我们实际使用的程序设计语言。如果去刻画的是参与计算的事物以及计算的每一个步骤，得到的就是C、Java这种我们熟悉的面向过程的、对象的语言；如果将过程封装起来，用输入与输出去刻画计算，那么得到的就是函数式编程语言；甚至还可以连计算的顺序都抛掉，去刻画使能条件，得到Prolog这种逻辑型语言。可以确定的是，这些不同视角下得到的语言在理论（可计算能力）上显然是等同的，在工程上显然是不同的，而这些不同的刻画是否本身就“本质地”反映了某些东西，却是一个很难回答的问题。

以上大约就是最近的一点学习心得，好像是在谈技术细节，又好像是在谈一些形而上的东西。不过这二者也分不开，我现在笃信类似世界观、方法论这种东西只有在科学实践中去体会、去谈论才是有意义的²。类似于“视角不同结论就不同”这种话，如果离开具体的技术细节，那么就和所谓一分为二、把握重点的辩证法一样，都是永远正确也永远没有意义的废话。这绝非说它们不重要，相反它们非常重要，就像Church-Turing Thesis恐怕比任何一个具体的定理都反映了更多、更“本质”的东西，只是说要去把握这些非得从最具体的问题做起不可。

顺便又到了期中退课的季节，不出意外我又要退掉一些课程了——这意味着我没机会修完CS双学位了。不过我一点也不失落，相反很开心。我修不完的主要原因，除了在温水煮青蛙中彻底浪费了两年光阴以外，就是我完全不清楚CS到底在做什么、要学些什么。也就在半年前这个时候，我还是懵懵懂懂的，只能选一些信科的数学课还有编程、算法课，因为学习它们我只需要在系统封装好的接口上做事情就可以了。也就是说，我只对下图中最顶部两层有些许了解，往下就是一头雾水，那些大礼包课程根本没可能修下来。不过现在事情悄然起了变化，这两个月时间自己仿佛一下子就明白了图上每一层究竟在做什么、有哪些是自己想去学习、需要去学习的。这样看来，是否修完双学位已经是不重要的事情了，毕竟如果我能保持现在的状态，认真学完几门理论课，并且做好编译和体系结构实习的话，不谦虚地说，老娘的CS水平这次是真的要精进了！

 

[1]  那是一本很薄的小册子，却完整证明了马季亚谢维奇定理——希尔伯特第十问题的否定解。

[2]  出于同样的理由，我认为当代分析哲学、科学哲学中的很大一部分子领域，所能做的事情非常有限。