非生命体能否实现自我复制？
[align=justify]
[align=justify]
今天在课本（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即可。
后记：感觉这个构造颇可以改造为一个推理作品的绝佳元素，不过我暂时想不出具体的实现。
[/align]
[/align]
17 条回复
还在高中，没有系统学习计算机科学的前信息学竞赛选手说一下自己的思路。
我曾经在loj做过一道类似的题目，程序输出源代码本身，这是我的代码。
[code]
#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;
}
[/code]
它利用了编译器__FILE__这个宏定义，表示代码文件名。运行这个程序A，它会打印源代码本身。
那么如果我们再写一个程序B，来控制它，运行程序A，输出到新的代码文件并编译，每新建了新的可执行文件就运行它，并用新的线程来控制它，重复这个过程，如果算力是理想化的，是否可以达成无限自我复制？
#7
苦文霸
MC
[quote="Gekoo" pid='2426' dateline='1586526883']
还在高中，没有系统学习计算机科学的前信息学竞赛选手说一下自己的思路。
我曾经在loj做过一道类似的题目，程序输出源代码本身，这是我的代码。
[code]
#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;
}
[/code]
它利用了编译器__FILE__这个宏定义，表示代码文件名。运行这个程序A，它会打印源代码本身。
那么如果我们再写一个程序B，来控制它，运行程序A，输出到新的代码文件并编译，每新建了新的可执行文件就运行它，并用新的线程来控制它，重复这个过程，如果算力是理想化的，是否可以达成无限自我复制？
[/quote]
我是个半吊子，没研究过病毒，不太懂真实的程序是怎么复制的orz（我猜肯定不会复制源代码）。就复制源代码自身而言，你的程序是可行的，只是不能移植到自我复制机器上。（本质上是编译后的程序复制源代码，不是自己复制自己）
又，好像有人做出了自我复制的分子机器，参见[size=medium][font=Calibri,sans-serif]Zykov et al., Self-reproducing Machines, 2005
程序方面还有个自我复制神经网络，因为看不懂，我就没看 [/font][size=medium]Oscar Chang, Hod Lipson, Neural Network Quine, 2018[/size][/size]
#8
很有递归的味道，毕竟递归就是把函数嵌入自己嘛。继续往这个方向思考的话，会发现最后这个程序的结构和 Y 组合子非常像，都是把同一段程序拷贝两遍，而且一份拷贝使用另一份拷贝作为参数。
#17