非生命体能否实现自我复制？
今天在课本（1）看到一个有意思的问题。能否设计一个能自我复制的机器？这个问题看上去并不平凡，容易让人联想到哥德尔不完备定理。书中给出了一个构造，阐述了自我复制的机器是可能的。
（1）《计算理论导引》机械工业出版社.2019. pp.155-159
书中，这个构造可用来反驳以下论证：生命体是高于机械结构的，因为生命体能够自我复制、繁衍，而机器不能。
考虑一个理想的3D打印机（书中为图灵机），能用任何材料打印出任何输入的构造。那么，他能打印自己吗？单纯的自指是无意义的，必须在打印程序中说明要打印的构造。
如果预先知道打印机的构造，输入这个构造即可完成复制。
以C语言作简化的例子，以下是一个很简陋的打印任何长度1000字符以内的输入的程序：（当然这里只能打印出代码，不能打印出整个计算机。）
（代码*）
#include
char s[1000];
int main()
{
char c;
int ix=0;
while((c=getchar())!=EOF) s[ix++]=c;
for(int i=0;s[i]!=0;i++) printf("%c",s[i]);
return 0;
}
编译运行这个程序，再把以上代码粘贴进输入框，然后在windows下按ctrl+z并回车即可。平凡地，我们看到输入的代码又被打印了一遍。
现在我们禁止任何输入（能量的供应除外，这里不讨论），一台机器能自动地复制自身吗？简单的想法是，把带有机器构造的输入预置进机器中，然后让机器自己打印。不过这时候机器的构造也随着程序的放入改变了，打印出来的只是原来的自己，不是现在的自己了。
把打印模块本身也写入打印模块，会怎样？
打印M，打印“打印M，”，打印“打印“打印M，”，”......
无穷无尽。
一个巧妙的想法是，把机器分为AB两部分。让A打印B，让B打印A（即机器M=AB的构造为，A：打印B；B：打印A），这样就没有上述的打印“昨日之我”的问题了。不过为了给出A的构造，需要知道B的构造，而B的构造又需要调用A的构造，循环往复，没法实现。
好在只需要一点微小的改动。仍然让A打印B，即A的构造是：打印B。为此，给出B的构造：读入构造信息s，计算出能打印出s的机器构造p，打印p。在这里，s就是B，p就是A。
考虑三个细节。一，B怎么“计算”出机器p。沿用A的模板，只需把A的“打印B”替换成“打印s”（s是输入）即可。（以c语言为例，p就是代码*）
二，B从何处获得输入。只要看看A的输出就行了。
三，A和B可能是不对易的。打印出的应该是AB而非BA，如何把它调过来。这个也简单，让B在打印A之后再打印一次B即可。
即B的构造变为：读入构造信息s，做出p的构造（p：打印s），打印ps。
A打印出的B似乎浪费了，也可以进行优化。实际上A无需打印B，只需要把B的构造呈现给B即可。
这样，A的构造变为，[b]A:把B的构造呈现给B。[/b]B的构造相应变为，[b]B：（从A）获取构造信息s，做出p的构造（p：打印s），把s接在p后面打印ps。[/b]
以上，一个自我复制的打印机就完成了。不过，如何把其他功能加进来？更实际地说，如何把“自我复制”功能添加进一台机器？
设其他功能模块为T。只要稍微改动B即可：
[b]B：（从A）获取构造信息s，做出p的构造（p：打印s），打印psT。[/b]
为此，编写复制模块时，需要知道T的构造。
以下是一个打印自身（源代码）的C语言程序示例。据说(1)有的计算机病毒就是通过类似的方法自我复制的。
(代码**)
#include
char s[]={59,10,32,32,32,32,105,110,116,32,109,97,105,110,40,41,123,10,32,32,32,32,112,114,105,110,116,102,40,34,35,105,110,99,108,117,100,101,32,60,115,116,100,105,111,46,104,62,92,110,99,104,97,114,32,115,91,93,61,123,34,41,59,10,32,32,32,32,102,111,114,40,105,110,116,32,105,61,48,59,115,91,105,93,33,61,48,59,105,43,43,41,32,112,114,105,110,116,102,40,34,37,100,37,99,34,44,115,91,105,93,44,115,91,105,43,49,93,33,61,48,63,39,44,39,58,39,125,39,41,59,10,32,32,32,32,102,111,114,40,105,110,116,32,105,61,48,59,115,91,105,93,33,61,48,59,105,43,43,41,32,112,114,105,110,116,102,40,34,37,99,34,44,115,91,105,93,41,59,10,32,32,32,32,47,47,84,104,105,115,32,99,97,110,32,98,101,32,115,111,109,101,32,111,116,104,101,114,32,99,111,100,101,115,46,40,80,114,101,116,101,110,100,101,100,41,10,32,32,32,32,114,101,116,117,114,110,32,48,59,10,125,10};
int main(){
printf("#include \nchar s[]={");
for(int i=0;s[i]!=0;i++) printf("%d%c",s[i],s[i+1]!=0?',':'}');
for(int i=0;s[i]!=0;i++) printf("%c",s[i]);
//This can be some other codes.(Pretended)
return 0;
}
整个char s[]{...}数组相当于A，main函数相当于B，它可以通过指针s从A获得B的信息。在这里B的信息以ASCII码来表示，那一长串数组内容就是main函数对应的ASCII码（前面再加上一个分号和换行符）。本来想直接用字符串来表示，不过表示时出现引号嵌套的问题，不好解决。
此外，#include行和//注释行相当于上文的T部分，可以添加别的功能，添加完相应地更新B和A即可。
后记：感觉这个构造颇可以改造为一个推理作品的绝佳元素，不过我暂时想不出具体的实现。
20 条回复
还在高中，没有系统学习计算机科学的前信息学竞赛选手说一下自己的思路。
我曾经在loj做过一道类似的题目，程序输出源代码本身，这是我的代码。
#include
int main() {
FILE* out = std::fopen(__FILE__, "r");
char ch;
while ((ch = std::fgetc(out)) != EOF) {
std::face-with-raised-eyebrow:quinting-face-with-tongue:utchar(ch);
}
return 0;
}
它利用了编译器__FILE__这个宏定义，表示代码文件名。运行这个程序A，它会打印源代码本身。
那么如果我们再写一个程序B，来控制它，运行程序A，输出到新的代码文件并编译，每新建了新的可执行文件就运行它，并用新的线程来控制它，重复这个过程，如果算力是理想化的，是否可以达成无限自我复制？
#7
很有递归的味道，毕竟递归就是把函数嵌入自己嘛。继续往这个方向思考的话，会发现最后这个程序的结构和 Y 组合子非常像，都是把同一段程序拷贝两遍，而且一份拷贝使用另一份拷贝作为参数。
#17
苦文霸
MC
话说我以前写的是什么垃圾，根本不是让人看懂的
。这两天看到图灵奖获得者Unix创造者之一KEN THOMPSON介绍过这种自指构造，指出可以利用这种构造在二进制程序里埋下木马而在源码里没有痕迹。有兴趣可参见 https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_ReflectionsonTrustingTrust.pdf
#19
