转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/70971767200822371557244/
今天看了下<<计算理论导引>>,是计算理论领域的知名权威MIT的Michael Sipser所撰写。果然一般来说，计算机科学的书还是要看国外的。主要讲了自动机与语言、可计算性和计算复杂性，很多东西比较偏理论，主要看了下里面的递归定理，自动机。
几个证明方法:例证，反证，构造，归纳，循环不变式。看到很多初等但还算比较有意思的题目，比如证明sqrt(2)的无理性，求和公式，实数的不可数，以及有理数的可数。
另外还有比较有趣的是递归定理，这个定理的应用比较好的一个例子是关于自打印程序的，一会再详细说明。
还有就是自动机，主要是出于对字符串匹配的关心来看了下，不过这里的匹配主要是关于正则表达式方面的。
不过其中一个思想引起了我的注意，就是如何将多个DFA转化为一个DFA，因为在字符串匹配中，CLRS上主要是单串匹配，而多串匹配的方法没有明确讲解。而利用自动机的方法，便可以根据多个模式串生成。然后剩下的问题就是如何利用这些多个自动机，合并为一个执行，这样便可以单次扫描。
而合并的思想就是将原来的两个自动机的状态组合表示为一个新的状态，这样如果原来有i和j个状态则新的就有i*j个。状态转移方程表示为$(<i,j>,input) =<$(i,input),$(j,input)> 。
自打印程序:一个程序，其执行结果是把程序自身打印出来。
一个很迷惑人的观点是，机床比螺丝复杂，汽车厂比汽车复杂，创造者要比被创造者复杂。而生命是可以自我复制的（繁殖），因此生命无法用机械原理来理解。假如是在1950年(DNA是1953年发现的)，你该如何反驳呢？我们的“自我打印”程序证明了，“创造者要比被创造者复杂”是错误的。我们的程序加以扩展，可以携带任意的信息，执行任意额外的动作，而仍可以完全复制自身，这就是计算理论中的“递归定理”。20世纪三四十年代，在现代电子计算机还没有诞生的时候，计算理论的先行者图灵、丘奇、哥德尔等就已经解决了“什么是计算”、“什么是可计算的”等深刻的问题。另外生命存在很多一个自我复制的系统，如DNA，其实计算机的病毒也有类似的行为。
下面先给出一个流传已广的c自打印程序：
int main(){char *s="int main(){char*s=%c%s%c;printf(s,24,s,24);return 0;}";printf(s,24,s,24);return 0;}
其实自打印的程序很具有模版化，可以分成两部分：AB
A的输出就是B的程序文字；
B部分可以得到Ａ部分的输出，同时可以根据Ａ部分的输出得到Ａ部分的程序文字，这样Ｂ便可以把ＡＢ的程序文字联合起来，ｐｒｉｎｔ即可。
所以对Ａ部分有两个要求：通过它的输出即要得到Ａ的程序文字，也能得到Ｂ的程序文字。
而在写Ａ的时候，通常通过一个字符串赋值完成，但是这个赋值需要等到Ｂ部分完成之后才能真正完成。首先Ａ将自身包含，然后写Ｂ部分，然后再Ａ中将Ｂ包含。
下面结合上述思想给出一个Ｃ＋＋的例子：
#include <iostream>
#include <string>
using namespace std;
int main (){string a="#include <iostream>T#include <string>Tusing namespace std;Tint main (){string a=;a[19]=a[37]=a[58]=10;cout<<a.substr(0,80)<<(char)34;a[19]=a[37]=a[58]=84;cout<<a<<(char)34<<a.substr(80);return 0;}";a[19]=a[37]=a[58]=10;cout<<a.substr(0,80)<<(char)34;a[19]=a[37]=a[58]=84;cout<<a<<(char)34<<a.substr(80);return 0;}
主要思想如上，在于使string a的值可以产生Ａ，Ｂ的代码
另外a[19]=10;a[37]=10;a[58]=10;和a[19]=84;a[37]=84;a[58]=84;
主要作用是将字符"T"换为回车符号然后打印完第一部分后还原为"T"。
仔细观察可以发现AB两部分都是由string a生成的。
a.substr(0,80)<<(char)34<<a<<(char)34实际上形成了A(从开头到a定义之后的;)
而a.substr(80)则是B部分（从cout到结束）