离奇的code

计算理论导引-如何编写自打印的程序

2008年3月23日 阅读(75)

转载请注明作者: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部分可以得到A部分的输出,同时可以根据A部分的输出得到A部分的程序文字,这样B便可以把AB的程序文字联合起来,print即可。

所以对A部分有两个要求:通过它的输出即要得到A的程序文字,也能得到B的程序文字。
而在写A的时候,通常通过一个字符串赋值完成,但是这个赋值需要等到B部分完成之后才能真正完成。首先A将自身包含,然后写B部分,然后再A中将B包含。

下面结合上述思想给出一个C++的例子:
#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,B的代码 
另外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到结束)

You Might Also Like