Quines(自我复制程序)

“quine”(或“selfrep”)是打印自己的列表的计算机程序。这听起来可能是不可能的，或微不足道的，或完全无趣的，这取决于你的脾气和你的计算机科学知识。实际上，这是可能的，而且涉及到一些有趣的想法(特别是，编写Quine不是一种只起作用的技巧，因为编程语言具有某些很好的属性-它是一般所谓的“不动点”定理的结果，它本身就是Cantor无处不在的对角线论点的一个实例)。

奎因是以引入这一概念的美国数学家和逻辑学家威拉德·范·奥曼·奎因(1908/06/25-2000/12/25)的名字命名的。这一页是用来纪念他的。

我还要把这一页献给道格拉斯·R·霍夫施塔特(Douglas R.Hofstadter)，他在他著名的著作“哥德尔、埃舍尔、巴赫”(Gödel，Escher，Bach)中创造了这个名字，并如此清晰地解释了Quines的重要性及其与Gödel的不完全性定理的关系。

Quine是一个打印自己列表的程序。这意味着当程序运行时，它必须准确地打印出程序员作为程序一部分编写的指令(当然，包括执行打印的指令和打印中使用的数据)。

当然，要做到这一点，最简单的方法是在磁盘上查找源文件，打开它，然后打印其内容。这是可以做到的，但这被认为是作弊；此外，程序可能不知道源文件在哪里，它可能只访问编译后的数据，或者编程语言可能简单地禁止这种操作。

有趣的是，编写Quine并不依赖于任何类型的技巧，比如能够读取源文件，甚至能够以几种不同的方式表示引号。任何一种程序设计语言，如果是图灵完全的，并且能够输出任何字符串(通过字符串的可计算函数作为程序-这是在现有的每种程序设计语言中都满足的技术条件)，都有一个Quine程序(实际上，有无限多的Quine程序，以及许多类似的好奇心)遵循不动点定理。此外，不动点定理是建构性的，所以构造Quuine仅仅是一个耐心的问题，而不是猜测(或一些人更喜欢称之为智力的工作)；-)。当然，这并不是说，实际上写一篇简短或有趣的奎因可能不需要太多的聪明才智。尽管如此，它说在奎恩后面没有什么“神奇”的东西；也没有说它们必须像往常一样被混淆、难以阅读或没有评论。

我们尝试用C语言编写Quine，我们选择C是因为它广为人知，还因为printf()函数具有使编写Quine变得相当容易的特性(这是一种喜忧参半的好处：它是一种收获，因为它使Quine变得更小，但它也使它变得更加晦涩和“黑客”)。

我们希望quine是正确的C代码，因此它可能必须开始如下内容：

我们要做的第一件事是打印前面的所有内容。我们可以天真地写道：

诸若此类。很明显，这是行不通的(除非我们打算产生无限长度的Quine，而我们并没有这样做)。

这种推理使一些人相信奎因是不存在的。问题是我们需要打印一些东西，所以我们使用一个字符串(比如s)来打印它，然后我们需要打印s本身，所以我们使用另一个字符串，依此类推…。

但是等等！如果我们打算打印s，我们不需要另一个字符串：我们可以使用s本身。所以让我们再试一次：

嗯，它还是不管用。但我们已经介绍了Quine写作知识中的一个核心思想：虽然可能需要使用一些数据来表示要打印的代码，但另一方面，可以重复使用这些数据来打印数据本身。在这里，我们仍然有些天真：我们正在使用s“原样”，但这样做是正确的，因为它包含一些反斜杠；这些反斜杠需要进一步反斜杠处理。因此，我们面前有两条路：王者之路是继续回溯，这是可行的，因为这是一个可计算的过程。但是，由于我们是用C语言编写的，所以我们选择了一个快捷方式，它使用了printffunction的良好属性：

char*s1="；#include<；stdio.h>；%c%cint%cmain(Void)%c{%c"；char*s2="；char*s1=%c%s%c；%c char*s2=%c%s%c；%c"；；char n='；\n'；，q='；"；'；；printf。printf(s2，q，s1，q，n，q，s2，q，n)；

这是一个Partial Quine：它打印自己清单的开头(这不是什么了不起的事情，因为任何不打印任何东西的程序都是“Partial Quine”)。这里我们已经过了“追赶点”，我的意思是打印的程序数据包括数据表示本身。然后，完成Quine通常是微不足道的(在这里，事情仍然有点棘手，因为我们一直或多或少地以一种临时的方式做事，而且一些数据实际上隐藏在printf()语句中。尽管如此，要完成并不是很困难：

#include<；stdio.h>；intmain(Void){char*s1="；#include<；stdio.h>；%c%cint%cmain(Void)%c{%c"；char*s2="；char*s%c=%c%s%c；%c char*s%c=%c%s%c；%c"；char*s3=&#。%c%c'；；%c"；；char*sp="；printf("；；char*s4="；%ss1，n，n)；%c"；；char*s5="；%ss2，'；1'；，q，s1，q，n，'；2'；，q，s2，q，n)；%ss2，'；3，q，s3，q，n，'；p'；，q，sp，q，n)；%c"；；char*s6="；%ss2，'；4'；，q，s4，q，n，'；5'；，q，s5，q，n)；%s2，'；6'；，q，s6，q，n，'；7'；，q，s7，q，n)；%c%ss2，'；8'；，q，s8，q，n，'；9'；，q，s9，q，n)；%ss2，'；0'；，q，s0，q，n，'；x'；，q，sx，q，n)；%c"；char*s8="；%ss3，b，q，b，b，n)；%ss4，sp，n)；%。char*s9="；%ss6，sp，sp，n)；%ss7，sp，sp，n)；%ss8，sp，n)；%c"；char*s0="；%ss9，sp，n)；%s0，sp，sp，n，n，n)；%c返回0；%c}%c"；char*sx="；--这是一个内含子。-"；；char n='；\n'；，q='；"；'；，b='；\\'；；printf(S1，n，n)；printf(S2，'；1'；，q，S1，q，n，'；2'；，q，S2，q，n)；printf(S2，'；3'；，q，s3，q，n，'；p'；，q，sp，q，n)；printf(s2，'；4'；，q，s4，q，n，'；5'；，q，s5，q，n)；printf(s2，'；6'；，q，s6，q，n，'；7'；，q，s7，q，n)；printf(s2，'；8'；9'；，q，s9，q，n)；printf(s2，'；0'；，q，s0，q，n，'；x'；，q，sx，q，n)；printf(s3，b，q，b，b，n)；printf(s4，sp，n)；printf(s5，sp，sp，n)；printf(s6，sp，sp，n)；printf(S7。printf(s9，sp，n)；printf(s0，sp，sp，n，n，n)；返回0；}

这里我们有一个真正的Quine(如果你觉得它晦涩难懂，别担心，下面会给出更清楚的例子)。请注意，使用S2字符串打印在同一图案上建模的几行。还要注意反斜杠是如何不需要特殊处理的，还要注意SX字符串，它表明Quine中的所有东西都必须加倍的传统观念是错误的(来自分子生物学的术语“内含子”的含义将在下面更加清楚)。

这个Quine是中等优雅的：一方面，它没有假设计算机使用的是ASCII字符集(您会看到很多C Quine使用双引号具有ASCII代码34，换行符具有代码10的事实)，它是有效的ANSIC(但是，注意到我应该写“conchar*”而不是只写“char*”；这比许多省略末尾返回0或类似内容的quine要好得多)，它是一种有效的ANSI C语言(但需要注意的是，我应该写“stchar*”而不仅仅是“char*”；这比许多省略末尾返回0或类似内容的quine要好得多)。另一方面，格式是不优雅的：不要从上面的例子中得出结论，Quines需要如此糟糕的呈现。而且，没有人说你不能在奎恩斯里有意见。稍后我们将给出更多优雅的例子。

(在大多数编程语言中)程序不可能直接操纵自身(即，它的文本表示-或者可以很容易地从它的文本表示导出的表示)。

为了实现这一点，我们从两个部分编写构建程序，一部分调用代码，另一部分称为数据。数据表示代码(的文本形式)，它是以算法的方式派生出来的(大多数情况下，通过在代码两边加引号，但有时会以稍微复杂的方式)。代码使用数据来打印代码(这很容易，因为数据代表代码)；然后它使用数据来打印数据(这是可能的，因为数据是通过代码的算法转换获得的)。

这一思想可以用“奎因”这句话来概括。这里，动词to quine(道格拉斯·R·霍夫施塔特发明)的意思是“第一次写(一个句子)，然后再写一次，但是用引号括起来”(例如，如果我们用引号“说”，我们得到的是“说‘说’”)。因此，如果我们对“quine”进行Quine，就会得到“quine‘quine’”，这样句子“quine‘quine’”就是quine…。在这种语言类比中，动词“to quine”扮演的是代码的角色，引号中的“quine”扮演的是数据的角色。

此后，我们将大量使用“代码”和“数据”这两个词来指定Quine的代码和数据部分，如上所述。

如果我们拿细胞生物学做类比(再次感谢道格拉斯·霍夫斯塔特)，我称之为“代码”的将是细胞，而“数据”将是细胞DNA：细胞能够利用DNA创造新的细胞，这其中包括复制DNA本身。因此，DNA(数据)包含复制所需的所有信息，但如果没有细胞(代码)或至少一些其他代码来使数据存活，它就是一条无用的、惰性的数据。

注意数据如何包含(取决于它的解释方式)位，这些位不是用来写代码的，而是在数据写入输出时被复制的。这些片段被称为内含子，类似于基因组中不用于生产蛋白质的部分。我们上面给出的例子有一个简单的介绍(字符串SX)，很清楚地标出了这样的标记。很明显，内含子可以非常容易地修改；它是一种潜意识信息，可以用Quine重现，尽管Quine不是必需的。内含子的可能存在将是使多个五元组成为可能的关键特征(这一点我们将在后面讨论)。

警告一句：quines中的这种代码/数据区分是令人愉快的，而且通常很有帮助。然而，它并不是在所有情况下都是完全有效的。有时代码和数据没有很好地区分，有时部分代码扮演数据角色，反之亦然。有些奎因远远超出了我自己的谦虚理解，也超出了我对分类和排序的无力尝试。就像在AllThings中一样，买者自负。不过，请看正文后面的这句话。

我们现在使用上面概述的原则来构造另一个Quine，它的格式会更优雅(但可移植性会稍差一些，因为我们将假设字符是ASCII编码)。

这一次，我们将所有数据收集到一个位置，一个包含组成代码的字符的ASCII值的数组，我们将这个数组放在程序的开头。代码将使用数组首先打印数组(通过将其打印为具有适当格式的十六进制整数列表)，然后打印代码(通过将ASCII值转换为字符)。

这完全是直截了当的，虽然这个奎恩远不是最短的，但我认为它是我见过的最清楚的：

/*参见下面的注释*/const无符号字符数据[]={/*000000*/0x2f，0x2a，0x20，0x54，0x68，0x69，0x73，0x20，/*0x0008*/0x69，0x73，0x20，0x61，0x20，0x73，0x65，0x6c，/*0x0010*/0x66，0x72，0x65，0x20。有关完整清单，请参阅原始文件。*//*0x02c0*/0x20、0x28、0x64、0x61、0x74、0x61、0x5b、0x69、/*0x02c8*/0x5d、0x29、0x3b、0x0a、0x20、0x20、0x72、0x65、/*0x02d0*/0x74、0x75、0x72、0x6e、0x20。它使用上面的数据(它*正是从该注释开始*的所有内容的ASCII表示形式)来打印它自己的清单。*/#include<；stdio.h>；intmain(Void)/*主程序。我们以此文件顶部使用的格式输出数据，然后使用它生成此文件的其余部分。*/{unsign int i；printf("；/*参见下面的注释*/\n\n"；)；printf("；const unsign char data[]={"；)；for(i=0；i<；sizeof(Data)；i++){if(i%8==0)printf("；\n/*%0#6x*/"；i)；printf}printf("；\n}；\n\n"；)；for(i=0；i<；sizeof(Data)；i++)putchar(data[i])；返回0；}。

这应该会让人很明显地看到，写五段诗没有任何困难。实际上，这就是我们直接应用不动点定理得到的一类五次方程。如上所述，代码包含两个部分：复制数据的部分(main()函数中空白一行之后的9行)和使用数据复制代码的部分(接下来的两行)。

当然，数据的编码可能比简单的ASCII编码复杂得多。我们将回到那个主题。还要注意，这里没有内含子，因为ASCII不允许这样(没有注释或任何类似的东西)。然而，我们可以简单地添加一个内含子：创建一个新数组，const unsign charinon[]，比如说，在其中放入我们想要的任何数据，并像我们对data[]所做的那样对内含子[]使用相同的打印例程(当然，我们需要修改代码，因此数据也需要这样做，但是一旦完成，我们就可以在内含子中放入任何东西，而不需要修改任何东西)。

另一点需要注意的是，在前面的内容中，我从数据中省略了很多行。如果我没有给你一个指向原始文件的指针，你能重建数据吗？显然，是的，而且没有太大的困难：只需取代码，取每个字符的ASCII值，并将它们制表即可。这违反了所谓的中央法则，规定必须使用数据(由代码)来推断(即打印)代码，而不是相反。然而，在实践中，违反CentralDogma没有什么错，事实上，您可以猜到我是通过首先编写引用然后计算数据来编写程序的；但是，内含子不能以这种方式重建(因为内含子的真正意义在于所有可能的数据都可以工作)。

如果代码的一部分丢失了怎么办？那么情况就好多了。例如，如果这些建议已经被吞噬，那么运行程序本身就会存储它们(从它们在数据中编码的值)。即使根本没有任何代码，您也可能会猜到数据是某物的ASCII表示，并且能够恢复有问题的某物。但有关这方面的更多信息，请参阅引导部分。

我已经提到了不动点定理，并指出它是奎因存在的核心。我现在来解释一下这个定理是怎么说的。

(请注意，这只是数学中大量不动点定理中的一个。例如，这与布劳沃的不动点定理无关。我不知道这个定理有没有什么具体的名字，但我怀疑它会有点像克莱恩的不动点定理。)。

我想我对可计算性理论不太熟悉。然而，它会有所帮助：如果你不熟悉它，我将要说的话可能听起来有点含糊(但无论如何要读一读，因为即使细节含糊，你也可能会理解它的意思)。

可计算的(或“通用递归”)函数(具有多个整数变量，并且具有整数值)是由某个程序(即，操作变量作为输入的某个图灵机，即某个算法，根据您想要采用的单词“算法”的任何定义，因为通过丘奇-特灵顿命题，它们都是等价的)计算的函数。我们的分部函数不一定定义在输入变量的所有可能值上。我们所说的总函数是指一个函数。

我们需要一个标准的节目编号。这也取决于所选择的可计算性模型，但是可以想象，假设将程序视为某个整数的二进制表示而获得的值与该程序相关联。我们写为φn(…)。对于第n个程序的结果，当输入由省略号表示的结果时。特别地，对于某个n，任何可计算函数都等于φn。我们不会从一个程序的相关数字来区分它。

普适性定理指出，(部分)函数φn被认为是n加上它的其他值的函数，它本身是可计算的。换句话说，存在一个u(如果你愿意，或者更简单地说，是一个解释器)，使得φu(n…)。=φn(…)。有效地说，这意味着您可以构造一个程序u，该程序u将接受程序n和一些参数，并返回应用于相关参数的n值。这意味着u是一个解释器，它接受程序并解释它，所以普适性定理仅仅说明了解释器的存在(所考虑的编程语言，用所考虑的编程语言编写)。普适性定理是丘奇-图灵论点的结果，即我们相信我们已经掌握了所有关于可计算性的概念。

s-m-n定理本质上是普适性定理的逆定理。它指出如果g(…)。=φn(…)。则对任意x，函数g(x…)是可计算的。=φn(x…)。(通过固定输入参数之一的值并让其保持变化而获得)是可计算的，并且是以可计算的方式从n开始获得的。也就是说，存在一个(可计算的、总的，实际上是本原递归的)函数s，使得φs(n，x)(…)。=φn(x…)。.如果编号做得正确，这实际上是微不足道的(事实上，它几乎是对编号正确这一事实的定义)：它表明，如果你有一个程序n接受一些输入，你可以(对于每个x)构造一个程序(n，x)，它将充当n，除非它接受x作为输入；而且，这个另一个程序是从第一个程序算法派生而来的。因此，实际上，您可以用值替代程序中的输入。

利用s-m-n定理和普适性定理证明了不动点定理。这说明对于任何可计算的总函数h，存在一个索引(程序)n使得φn(…)。=φh(N)(…)。。

简而言之，这意味着如果你对程序有任何算法变换h，那么就存在一个程序n，使得程序n和变换产生的程序n做同样的事情。我们将在第二节用更多的例子来解释这一点，但首先我们要证明这一说法。

对于给定的程序t，我们考虑程序(t，t)(由s-m-n定理给出)。本质上，s(t，t)执行t作为输入时执行的操作。进一步考虑程序h(s(t，t))，它由变换h应用于s(t，t)，现在根据普适性定理，存在一个指标m使得φm(t…)。=φh(s(t，t))(…)。换言之，存在将程序t作为输入并执行程序h(s(t，t))所做的事情的程序m。然后我断言程序n=s(m，m)是期望的不动点。事实上，φn(…)。=φs(m，m)(…)。.但是根据s的定义，这是φm(m…)。，根据m的定义，它又是φh(s(m，m))(…)。=φh(N)(…)。，这是一份示威性的备忘录。

综上所述，我们以给定程序t的程序m为例，它解释了将给定的变换h应用于t本身所产生的程序结果，并且我们已将该程序应用于其自身。

不动点定理是如何证明的。

..