更改

虽然提起自指，人们很容易想到自指悖轮。但是，人们不熟悉的是另外一大类无害的自指，它们通常直接应用蒯恩技术，而实现某些意想不到的结构或者功能。下面，让我们先从一种最简单的建构性自指：自打印程序说起。

虽然提起自指，人们很容易想到自指悖轮。但是，人们不熟悉的是另外一大类无害的自指，它们通常直接应用蒯恩技术，而实现某些意想不到的结构或者功能。下面，让我们先从一种最简单的建构性自指：自打印程序说起。

所谓的程序自打印就是指一个程序能够在'''不读取外部文件'''的条件下把自己的源代码打印出来。首先，我们要先领教一下，一个自我打印的程序是多么不可能的！我们知道，要写一个程序打印出“helloworld!”字样是非常容易的，例如：

所谓的程序自打印就是指一个程序能够在'''不读取外部文件'''的条件下把自己的源代码打印出来。首先，我们要先领教一下，一个自我打印的程序是多么不可能的！我们知道，要写一个程序打印出“helloworld!”字样是非常容易的，例如：

其中\\就表示包含一个字符“\”的字符串变量，这样Print(‘\\’)就会打印出一个字符“\”，而Print(‘\\\’’)就会打印出字符串“\’”出来。所以，引号里面可以放入任意层次的引号。

其中\\就表示包含一个字符“\”的字符串变量，这样Print(‘\\’)就会打印出一个字符“\”，而Print(‘\\\’’)就会打印出字符串“\’”出来。所以，引号里面可以放入任意层次的引号。

但是这个程序仍然不能打印自己！你很快发现，我们人类是写不出这种能够打印自己的程序的，因为它包含了无穷递归。不过，通过蒯恩技巧，实际上我们完全可以写出来一个自打印程序，如下：

但是这个程序仍然不能打印自己！你很快发现，我们人类是写不出这种能够打印自己的程序的，因为它包含了无穷递归。不过，通过蒯恩技巧，实际上我们完全可以写出来一个自打印程序，如下：

“+”表示将两个字符串进行串联形成一个新的字符串，例如<code>A=’123’,B=’456’，则A+B=’123456’</code>。

“+”表示将两个字符串进行串联形成一个新的字符串，例如<code>A=’123’,B=’456’，则A+B=’123456’</code>。

这个自打印程序调用了一个简单的解码函数<math>p(q)</math>，<math>p</math>的作用是将字符串<math>q</math>变换成更浅一层次的字符串。例如，如果<math>q</math>是“\\\’\\’\\n\\”，那么<math>p</math>这个函数就会计算输出“\’’\n\”。也就是说<math>p</math>完成了一组映射：它把“\\”映射成“\”，把“\’”映射成“’”，而把“\n”映射成回车符。显然<math>p</math>是可以写出来的。我们知道，由引号的引用可以形成更加深层次的虚拟世界（参见上一小节）。所以<math>p(q)</math>的作用就是让字符串<math>q</math>弹出一层虚拟世界。由于<math>p</math>的作用很简单，我们假设它是一个系统自带的函数，因此就不在源代码1中给出<math>p</math>的实现代码了。

这个自打印程序调用了一个简单的解码函数<math>p(q)</math>，<math>p</math>的作用是将字符串<math>q</math>变换成更浅一层次的字符串。例如，如果<math>q</math>是“\\\’\\’\\n\\”，那么<math>p</math>这个函数就会计算输出“\’’\n\”。也就是说<math>p</math>完成了一组映射：它把“\\”映射成“\”，把“\’”映射成“’”，而把“\n”映射成回车符。显然<math>p</math>是可以写出来的。我们知道，由引号的引用可以形成更加深层次的虚拟世界（参见上一小节）。所以<math>p(q)</math>的作用就是让字符串<math>q</math>弹出一层虚拟世界。由于<math>p</math>的作用很简单，我们假设它是一个系统自带的函数，因此就不在源代码1中给出<math>p</math>的实现代码了。

S(x)这个程序中包含了过多的“\”和“’”符号，这就导致我们理解源代码1稍显困难，下面我们将把该程序表示成下面的图，从而让读者看得更清晰一些：

S(x)这个程序中包含了过多的“\”和“’”符号，这就导致我们理解源代码1稍显困难，下面我们将把该程序表示成下面的图，从而让读者看得更清晰一些：

[[File:jake20111317131552.jpg |thumb |center |400px | 图5-2、自打印程序源代码中的引号层次示意]]

[[File:jake20111317131552.jpg |thumb |center |400px | 图5-2 自打印程序源代码中的引号层次示意]]

如上图，这个自打印程序中的引号全部用方框来替代。这样第一层引号’…’就对应了第一层的方框，引号中的引号，即“\’…\’”就对应了框中的一个框。这样，由于程序中出现最多的层次是四层引号，即“\\\’”，所以上图中就出现了第四层框。

如上图，这个自打印程序中的引号全部用方框来替代。这样第一层引号’…’就对应了第一层的方框，引号中的引号，即“\’…\’”就对应了框中的一个框。这样，由于程序中出现最多的层次是四层引号，即“\\\’”，所以上图中就出现了第四层框。

另外，我们还观察到，这个程序包含了两个大框，即“q=”后面的黄框和“Print()”之中的那个蓝框。这两个框的结构是完全一样的，只不过黄框比蓝框多了一个虚拟层次，这反映在所有的蓝色框中的最深一层框都再加上一层框就得到了黄色框。

另外，我们还观察到，这个程序包含了两个大框，即“q=”后面的黄框和“Print()”之中的那个蓝框。这两个框的结构是完全一样的，只不过黄框比蓝框多了一个虚拟层次，这反映在所有的蓝色框中的最深一层框都再加上一层框就得到了黄色框。

更有趣的是，整个程序S(x)实际上和这两个框是相似的，因此这个程序本身就是一个分形结构。在传统的分形结构中，每一个部分都会包括无穷多的细节。但是，在这个自打印程

更有趣的是，整个程序S(x)实际上和这两个框是相似的，因此这个程序本身就是一个分形结构。在传统的分形结构中，每一个部分都会包括无穷多的细节。但是，在这个自打印程

序中，虽然有嵌套的分形结构，但是却没有达到无穷，最深的引号也仅仅有4层。

序中，虽然有嵌套的分形结构，但是却没有达到无穷，最深的引号也仅仅有4层。

让我们来分析一下这个程序是如何运作的。首先，看程序的最后一行，即<code>Print(‘S(x){\nq=\’’+q+’\’;\nPrint(\’’+p(q)+’\’);\n}’);</code>这句话的作用是让程序在屏幕上打印出一个字符串。注意观察，这个被打印出的字符串其实是由“+”号被分割成了5个部分，第一部分是<code>“S(x){\nq=\’”</code>，第二个部分是q这个字符串的原封不动的拷贝，第三部分是字符串：<code>“\’;\nPrint(\’”</code>，第四部分是函数<math>p</math>作用到<math>q</math>上面的结果即<math>p(q)</math>；第五部分还是一个字符串：<code>“\’);\n}”</code>。然后当我们把q字符串的数值代入第二部分和第四部分，并进行运算<math>p</math>之后，就得到了和源程序一模一样的结果。你不妨在计算机上运行这段程序，就会发现这段程序会在屏幕上赤裸裸地把自己的源代码打印出来。

让我们来分析一下这个程序是如何运作的。首先，看程序的最后一行，即<code>Print(‘S(x){\nq=\’’+q+’\’;\nPrint(\’’+p(q)+’\’);\n}’);</code>这句话的作用是让程序在屏幕上打印出一个字符串。注意观察，这个被打印出的字符串其实是由“+”号被分割成了5个部分，第一部分是<code>“S(x){\nq=\’”</code>，第二个部分是q这个字符串的原封不动的拷贝，第三部分是字符串：<code>“\’;\nPrint(\’”</code>，第四部分是函数<math>p</math>作用到<math>q</math>上面的结果即<math>p(q)</math>；第五部分还是一个字符串：<code>“\’);\n}”</code>。然后当我们把q字符串的数值代入第二部分和第四部分，并进行运算<math>p</math>之后，就得到了和源程序一模一样的结果。你不妨在计算机上运行这段程序，就会发现这段程序会在屏幕上赤裸裸地把自己的源代码打印出来。

我们不妨把这段程序的5个部分进行归并，写成由下面的三部分构成的：<math> (Copy_o \  Popup_o \  Control)</math>，其中Copy就是5部分中的第二部分，即相当于一个拷贝字符串的程序，你输入

我们不妨把这段程序的5个部分进行归并，写成由下面的三部分构成的：<math> (Copy_o \  Popup_o \  Control)</math>，其中Copy就是5部分中的第二部分，即相当于一个拷贝字符串的程序，你输入

给Copy什么字符串，Copy就会把那个字符串再原封不动地吐出来；Popup这部分就是原来的5部分中的第四部分，即函数<math>p</math>，它的作用相当于一个弹出操作，也就是为输入的字符

给Copy什么字符串，Copy就会把那个字符串再原封不动地吐出来；Popup这部分就是原来的5部分中的第四部分，即函数<math>p</math>，它的作用相当于一个弹出操作，也就是为输入的字符

串脱去一层引号。如果输入的字符串原来是在第<math>n</math>层虚拟世界，则Popup的作用就是让字符串跳到第<math>n-1</math>层；最后Control这部分就相当于原来的第1、3、5这三部分以及最一开始的语句Print的总合，它的作用就相当于是为Copy和Popup制造出来的字符添加适当的连接词，使得最后的字符串能够拼接成与原来的程序一模一样的源程序，并将其打印到屏幕上。所以这句<code>“Print(‘S(x){\nq=\’’+q+’\’;\nPrint(\’’+p(q)+’\’);\n}’);”</code>就可以改写成<math> (Copy_o \  Popup_o \  Control)(q)</math>。其中“о”表示将不同的程序连接为一体。

串脱去一层引号。如果输入的字符串原来是在第<math>n</math>层虚拟世界，则Popup的作用就是让字符串跳到第<math>n-1</math>层；最后Control这部分就相当于原来的第1、3、5这三部分以及最一开始的语句Print的总合，它的作用就相当于是为Copy和Popup制造出来的字符添加适当的连接词，使得最后的字符串能够拼接成与原来的程序一模一样的源程序，并将其打印到屏幕上。所以这句<code>“Print(‘S(x){\nq=\’’+q+’\’;\nPrint(\’’+p(q)+’\’);\n}’);”</code>就可以改写成<math> (Copy_o \  Popup_o \  Control)(q)</math>。其中“о”表示将不同的程序连接为一体。

如果我们把一个计算机程序<math>X</math>的描述（或者称源代码）写为<math>\lambda(X)</math>，则自打印程序的第一条赋值语句就相当于给<math>q</math>赋予了<math>\lambda (Copy_o \  Popup_o \  Control)</math>，即<math> (Copy_o \  Popup_o \  Control)</math>这三个程序连在一起的源代码。最后我们可以将自打印程序简写为：

如果我们把一个计算机程序<math>X</math>的描述（或者称源代码）写为<math>\lambda(X)</math>，则自打印程序的第一条赋值语句就相当于给<math>q</math>赋予了<math>\lambda (Copy_o \  Popup_o \  Control)</math>，即<math> (Copy_o \  Popup_o \  Control)</math>这三个程序连在一起的源代码。最后我们可以将自打印程序简写为：

我们可以进一步地把它简写为：<math>Q(q)</math>，其中<math>Q</math>表示(<math>(Copy_o \  Popup_o \ Control)</math>)这三个程序的联合程序，而<math>q</math>则表示联合程序的源代码。<math>Q(x)</math>这个程序的作用是输出一个特殊的字符串“<math>X(x)</math>”即程序<math>X</math>调用自己的代码x的源程序，我们称这个<math>Q</math>为'''蒯恩函数'''。

我们可以进一步地把它简写为：<math>Q(q)</math>，其中<math>Q</math>表示(<math>(Copy_o \  Popup_o \ Control)</math>)这三个程序的联合程序，而<math>q</math>则表示联合程序的源代码。<math>Q(x)</math>这个程序的作用是输出一个特殊的字符串“<math>X(x)</math>”即程序<math>X</math>调用自己的代码x的源程序，我们称这个<math>Q</math>为'''蒯恩函数'''。

那么，自打印程序不是别的，正是将蒯恩函数<math>Q</math>自己的源代码再喂给它自己，这样就产生了<math>Q(q)=</math>"<math> Q(q)</math>"的效果。等式左边是<math>Q</math>对<math>q</math>的计算，是一个动作，它的结果产生了等式右边的字符串"<math>Q(q)</math>"，而这个字符串恰恰就是<math>Q</math>作用于<math>q</math>的源代码。我们看到，第2节中的蒯恩方法与这里的<math>Q(q)</math>是一模一样的。仔细想想不难发现，其实自打印程序的逻辑与蒯恩语句的逻辑是相通的。因此，自指恰恰就隐藏在了这段自打印程序之中了。

那么，自打印程序不是别的，正是将蒯恩函数<math>Q</math>自己的源代码再喂给它自己，这样就产生了<math>Q(q)=</math>"<math> Q(q)</math>"的效果。等式左边是<math>Q</math>对<math>q</math>的计算，是一个动作，它的结果产生了等式右边的字符串"<math>Q(q)</math>"，而这个字符串恰恰就是<math>Q</math>作用于<math>q</math>的源代码。我们看到，第2节中的蒯恩方法与这里的<math>Q(q)</math>是一模一样的。仔细想想不难发现，其实自打印程序的逻辑与蒯恩语句的逻辑是相通的。因此，自指恰恰就隐藏在了这段自打印程序之中了。

我们只要对这个自打印程序稍加更改就能创造出自我复制的程序出来。首先，我们要说明程序的自我复制究竟是什么意思。假设内存中漂浮着很多大大小小的程序，某一个程序P能够自我复制是指，当CPU执行到程序P的时候，P就会命令CPU执行一系列的操作使得它自己的一份拷贝会出现在内存中。但是，需要强调的是P不能够从硬盘上读取文件，否则自我复制将变得异常简单，只要把硬盘上的源程序再调用到内存中就行了。乍一看，这似乎与自打印程序一样不可能实现。但是利用与自打印程序同样的蒯恩技巧，我们依然可以很轻松地构造出自复制的程序出来。

我们只要对这个自打印程序稍加更改就能创造出自我复制的程序出来。首先，我们要说明程序的自我复制究竟是什么意思。假设内存中漂浮着很多大大小小的程序，某一个程序P能够自我复制是指，当CPU执行到程序P的时候，P就会命令CPU执行一系列的操作使得它自己的一份拷贝会出现在内存中。但是，需要强调的是P不能够从硬盘上读取文件，否则自我复制将变得异常简单，只要把硬盘上的源程序再调用到内存中就行了。乍一看，这似乎与自打印程序一样不可能实现。但是利用与自打印程序同样的蒯恩技巧，我们依然可以很轻松地构造出自复制的程序出来。

我们只需要把自打印程序(<math>(Copy_o \ Popup_o \  Control)</math>)中的<math> Popup_o </math>改成Construct就可以了。这里的Construct是一个函数，你输入给Construct一段程序的源代码<math>x</math>，它就能把<math>x</math>所对应的程序<math>X</math>编译出来并驻留在内存中。这样，程序<math>q=\lambda (Copy_o \ Popup_o \  Control)</math>就可以完成自复制功能。

我们只需要把自打印程序(<math>(Copy_o \ Popup_o \  Control)</math>)中的<math> Popup_o </math>改成Construct就可以了。这里的Construct是一个函数，你输入给Construct一段程序的源代码<math>x</math>，它就能把<math>x</math>所对应的程序<math>X</math>编译出来并驻留在内存中。这样，程序<math>q=\lambda (Copy_o \ Popup_o \  Control)</math>就可以完成自复制功能。

进一步，利用同样的逻辑，我们也能够制造出可以复制自身的真实机器。只要让Construct代表从给定机器的描述<math>\lambda (X)</math>而构造出实际机器<math>X</math>就行了。在冯诺依曼的著作《自复制自动机理论（[https://book.douban.com/subject/2982694/ Theory of Self-reproducing Automata]）》一书中，作者试图构建的自复制自动机就包括了这四个部分。即自复制机器是由一个通用拷贝机（Copy）、一个通用构造机（Construct）和一个控制器（Control）以及所有这三台机器的描述即源代码<math>q=\lambda (Copy_o \  Popup_o \  Control)</math>构成的。

进一步，利用同样的逻辑，我们也能够制造出可以复制自身的真实机器。只要让Construct代表从给定机器的描述<math>\lambda (X)</math>而构造出实际机器<math>X</math>就行了。在冯诺依曼的著作《自复制自动机理论（[https://book.douban.com/subject/2982694/ Theory of Self-reproducing Automata]）》一书中，作者试图构建的自复制自动机就包括了这四个部分。即自复制机器是由一个通用拷贝机（Copy）、一个通用构造机（Construct）和一个控制器（Control）以及所有这三台机器的描述即源代码<math>q=\lambda (Copy_o \  Popup_o \  Control)</math>构成的。

在此小节中，我们用自打印程序和自复制程序为例来说明了建构型的自指。然而，建构性的自指实际上不仅仅是这两种，它还会有各种各样的用途。下一节，我们将介绍著名的克林尼（Kleene）的递归定理，而自打印程序和自复制程序都仅仅是递归定理的一个逻辑推论。

在此小节中，我们用自打印程序和自复制程序为例来说明了建构型的自指。然而，建构性的自指实际上不仅仅是这两种，它还会有各种各样的用途。下一节，我们将介绍著名的克林尼（Kleene）的递归定理，而自打印程序和自复制程序都仅仅是递归定理的一个逻辑推论。