Empty Space - 写个程序，输出它自己的源代码

看看LOJ上的这道题：LOJ #4 Quine。

编写一个程序，输出自己的源代码。N年前LOJ上的这道测试用题让我想了半天，当时想不出来，去讨论区看了题解，基本上全是用printf的特性完成的。

最近半年断断续续在看《计算理论导引》（Introduction to Computation Theory 3e, Michael Sipser），有些部分着实看了挺过瘾的。特别是第六章提到的递归定理。

这个定理一句话简单概括就是：让图灵机输出自己的描述是可能的。换句话说，可以构造出一个图灵机 $M$ ，它输出自己的描述 $\langle M \rangle$ 。在实践中，意味着用任何编程语言都能写出一段程序，打印它自己的源代码——理解了递归定理的思路，解决这种简直易如反掌。

递归定理的简单证明思路

首先我们描述一个事实（这里不证明）：存在一个图灵机 $Q$ ，给字符串 $w$ ， $Q$ 可以立刻构造出打印 $w$ 的图灵机 $q(w)$ （也就是给个空白纸带作为输出， $q(w)$ 一定能停机，并且停机的时候纸带上是 $w$ ）。

引理1

存在可计算函数 $q: \Sigma^* \to \Sigma^*$ ，对任意串 $w$ ， $q(w)$ 是图灵机 $P_w$ 的描述。 $P_w$ 打印出 $w$ ，然后停机。

有了引理1之后，事情就简单了。我们可以构造出输出自己描述的图灵机 $\langle SELF \rangle$ 。

逻辑上可以把这个图灵机分成两部分： $A$ 和 $B$ 。我们让 $A$ 输出 $B$ 的源代码，让 $B$ 输出 $A$ 的源代码……等等，那不就死循环了吗？ $A$ 要输出 $B$ 的描述，那么 $A$ 的源代码里就要包含 $B$ 的源代码，反之亦然——这在逻辑上是做不到的，除非二者的源代码可以无限长（这当然是不行的）。

事实上利用引理1，我们可以巧妙地避免这种死循环。我们令 $B$ 为引理1中的 $Q$ ，令 $A = q(\langle B \rangle)$ 。

可能有点绕，需要稍微动点脑筋。任给一个字符串 $w$ ， $B$ 可以马上构造出一个图灵机 $q(w)$ ， $q(w)$ 的作用是打印 $w$ 。 $A$ 则就是 $q(\langle B \rangle)$ ，也就是把 $B$ 的源代码打印出来。如此一来，我们先执行 $A$ ，执行完之后纸带上的内容就是 $B$ 的源代码 $\langle B \rangle$ 。我们再把这个纸带交给 $B$ ，此时 $w = \langle B \rangle$ ，故执行完 $B$ ，纸带上的就是“输出 $\langle B \rangle$ 的图灵机”的源代码——即A的源代码！

我们只要稍微修改一下 $A$ 和 $B$ ，使二者打印的时候调换一下顺序， $\langle SELF \rangle$ 就构造出来了！

                      ┌─────────┐                                     
                      │         │                                     
                      │ program │                                     
     <Empty Tape> ────>         ├─────> <source code of B>            
                      │    A    │                                     
                      │         │                                     
                      └─────────┘                                     
                                                                      
                                                                      
                      ┌─────────┐                                     
                      │         │                                     
                      │ program │                                     
     "sadksjk..." ────>         ├─────> <source code of a program     
    │            │    │    B    │        which prints "sadksjk...">   
    └─────┬──────┘    │         │                                     
          │           └─────────┘                                     
       string w

C语言代码

下面步入正题——怎么写这样一个程序。

因为C语言需要引入头文件，也需要有个main函数，因此我们需要稍稍扩展一下上面的结论。我们把程序分成4段， $P$ 、 $A$ 、 $B$ 、 $Q$ ，如下：

下面用表示“P部分的源代码”，以此类推。可知<A><Q>即为我们需要输出的程序源代码。

P：程序的开头部分，到函数a()之前，作用略。escape()函数单纯是在适当的位置加上\，以便用printf输出（比如"helloworld\n"应该变成\"helloworld\\n\"）
A：函数a()，作用是将、、<Q>分别写进bufp、bufb、bufq
B：函数b()，作用是利用三个buf中已有的信息，构造出<A>，写入bufa（这一部分是关键）
Q：main函数，作用是把四个buf（也就是<A><Q>）按照顺序输出（复制粘贴的时候要注意末尾换行符）

代码如下：

#include <stdio.h>
#include <stdlib.h>

char bufp[10000];
char bufq[10000];
char bufb[10000];
char bufa[10000];

char* escape(char *buf) {
    char* nb = (char*)malloc(10000);
    char *base = nb;
    while (*buf) {
        if (*buf == '\n') {
            *nb = '\\'; ++nb;
            *nb = 'n'; ++nb;
        } else if (*buf == '\"') {
            *nb = '\\'; ++nb;
            *nb = '\"'; ++nb;
        } else if (*buf == '\\') {
            *nb = '\\'; ++nb;
            *nb = '\\'; ++nb;
        } else if (*buf == '\'') {
            *nb = '\\'; ++nb;
            *nb = '\''; ++nb;
        } else {
            *nb = *buf; ++nb;
        }
        ++buf;
    }
    *nb = '\0';
    return base;
}

void a() {
    sprintf(bufp, "%s", "#include <stdio.h>\n#include <stdlib.h>\n\nchar bufp[10000];\nchar bufq[10000];\nchar bufb[10000];\nchar bufa[10000];\n\nchar* escape(char *buf) {\n    char* nb = (char*)malloc(10000);\n    char *base = nb;\n    while (*buf) {\n        if (*buf == \'\\n\') {\n            *nb = \'\\\\\'; ++nb;\n            *nb = \'n\'; ++nb;\n        } else if (*buf == \'\\\"\') {\n            *nb = \'\\\\\'; ++nb;\n            *nb = \'\\\"\'; ++nb;\n        } else if (*buf == \'\\\\\') {\n            *nb = \'\\\\\'; ++nb;\n            *nb = \'\\\\\'; ++nb;\n        } else if (*buf == \'\\\'\') {\n            *nb = \'\\\\\'; ++nb;\n            *nb = \'\\\'\'; ++nb;\n        } else {\n            *nb = *buf; ++nb;\n        }\n        ++buf;\n    }\n    *nb = \'\\0\';\n    return base;\n}\n\n");
    sprintf(bufb, "%s", "void b() {\n    char *p = escape(bufp), *b = escape(bufb), *q = escape(bufq);\n    sprintf(bufa, \"void a() {\\n    sprintf(bufp, \\\"%%s\\\", \\\"%s\\\");\\n    sprintf(bufb, \\\"%%s\\\", \\\"%s\\\");\\n    sprintf(bufq, \\\"%%s\\\", \\\"%s\\\");\\n}\\n\\n\", p, b, q);\n    free(p); free(b); free(q);\n}\n\n");
    sprintf(bufq, "%s", "int main() {\n    a();\n    b();\n    printf(\"%s%s%s%s\", bufp, bufa, bufb, bufq);\n}\n");
}

void b() {
    char *p = escape(bufp), *b = escape(bufb), *q = escape(bufq);
    sprintf(bufa, "void a() {\n    sprintf(bufp, \"%%s\", \"%s\");\n    sprintf(bufb, \"%%s\", \"%s\");\n    sprintf(bufq, \"%%s\", \"%s\");\n}\n\n", p, b, q);
    free(p); free(b); free(q);
}

int main() {
    a();
    b();
    printf("%s%s%s%s", bufp, bufa, bufb, bufq);
}

C++代码

实际上可以不用printf。利用C++11引入的raw string，还可以把esacpe函数去掉。

#include <iostream>
#include <sstream>
#include <string>

std::string P, A, B, Q;

void a() {
    std::stringstream ss1, ss2, ss3;
    ss1 << R"(#include <iostream>
#include <sstream>
#include <string>

std::string P, A, B, Q;

)";
    ss2 << R"(void b() {
    std::stringstream ss;
    ss << "void a() {\n    std::stringstream ss1, ss2, ss3;\n    ss1 << R\"(" << P << ")\";\n    ss2 << R\"(" << B << ")\";\n    ss3 << R\"(" << Q << ")\";\n    P = ss1.str();\n    B = ss2.str();\n    Q = ss3.str();\n" << "}\n\n";
    A = ss.str();
}

)";
    ss3 << R"(int main() {
    a();
    b();
    std::cout << P << A << B << Q;
}

)";
    P = ss1.str();
    B = ss2.str();
    Q = ss3.str();
}

void b() {
    std::stringstream ss;
    ss << "void a() {\n    std::stringstream ss1, ss2, ss3;\n    ss1 << R\"(" << P << ")\";\n    ss2 << R\"(" << B << ")\";\n    ss3 << R\"(" << Q << ")\";\n    P = ss1.str();\n    B = ss2.str();\n    Q = ss3.str();\n" << "}\n\n";
    A = ss.str();
}

int main() {
    a();
    b();
    std::cout << P << A << B << Q;
}

充分利用语言特性，可以把程序压得更短，但是可读性可能就会大打折扣。

这东西有什么用

很有意思
这意味着可以写出一个自我“增殖”的程序（怎么听着有点像病毒）
这意味着可以做到让机器增殖
事实上任何图灵机稍微做个修改，都能输出自己的源代码，用这个方法可以简单证明 $A_{\mathrm{TM}}$ 是不可判定的。

$A_\mathrm{TM} = \{\langle M, w \rangle | M\text{是一个图灵机，且接受}w\}$