神奇的自产生程序，兼谈人工生命

最后更新日期：2013-11-22

　　最近读到冯·诺依曼的《Theory of Self-Reproducing Automata》的中译本，被自复制自动机理论深深吸引了！

　　生命是什么？这本书让我对生命有了新的认识。

　　热力学第二定律是宇宙的死亡法则：系统的熵总是趋于增加，系统总是由有序趋向无序，由有形趋向混沌，最后终结于热寂。宇宙万物都逃不过这条法则，唯有生命例外。通过与外界交换能量，生命可以保持内在的有序。只有生命可以违抗热力学第二定律。

　　热力学与信息论有着内在联系：一个系统越有序，它包含的信息就越多；一个系统越无序，它包含的信息就越少。信息总是沿着减少的方向流动。只有生命可以抗拒这个规律：生命可以“创造”出信息。“创造”是生命之所以为生命的本质。

　　生命的另一个神奇之处是，他们自己包含了自己的全部信息，他们自己可以产生一个跟自己一样的新生命。唯有生命可以做到自己创造自己。

　　冯·诺依曼认为，一个简单的系统是无法抗拒热力学第二定律的，这样的系统只会越来越趋向于无序，能量会向更低的方向流动，信息会越来越少。只有当系统复杂到某一个程度的时候，不妨设为临界点 C ，一旦越过了这个临界点，系统可以自己创造自己，这样系统就可以逆热力学第二定律而上，并且变得越来越复杂。

　　这里的临界点 C 跟不少人提出的“技术奇异点”是一样的：人们认为，当人工智能达到了这样一种程度，即它们可以自己创造自己的时候，这就是人工智能真正觉醒的时候。“奇异点”就是机器可以自己造出自己的时候，“奇异点”之后，机器将进化，并且变得越来越复杂，超出人类所能理解的范围，它们在某种程度上已经具备了生命的特质，那将是人工智能的时代。

　　总而言之，生命之所以区别于世界万物，就在于生命可以包含自己的全部信息。所以下面就是我们的问题了：

问题（自产生程序）：编写一个程序，不读取任何输入，只把自己的源代码输出。

　　这个问题是个非常本质的问题，跟使用什么编程语言无关（不要想到使用反射之类的东西）。

　　试想，如果要输出自己的源代码，那么，显然，程序中应该有“print …”语句。但 print 什么出来呢？如果硬要写的话就会变成：

print "print \"print ......\""

　　最后是一个无限循环。

　　一般地，我们知道，如果程序 A 能产生程序 B ，那么 A 必须包含 B 的全部信息，而且应该比 B 的信息还多，因为还要包含额外的打印语句。也就是说，一般情况下，信息是减少的。而这个自产生程序，自己要包含自己的全部信息，从某种程度上已经具有生命的意味了。

　　下面列出一些自产生程序及其思路。

　　需要注意的是，使用编程语言本身的反射功能或者读取文件等做法都被视为 cheating ，比如这样的 bash 脚本：

#!/bin/sh
cat $0

　　或者像这样的 javascript ：

function a() { console.log(a.toString(), "a()"); } a()

　　因为这些程序没有体现出自产生程序的递归和自指特性，或者结果严重依赖于编程语言的具体实现。

输出源代码在该语言中的转义

　　Python ：

s = "'s = ' + repr(s) + '\\nprint(' + s + ')'"
print('s = ' + repr(s) + '\nprint(' + s + ')')

　　Lua 5.1 ：

s = "string.format('s = %q\\nprint(%s)', s, s)"
print(string.format('s = %q\nprint(%s)', s, s))

　　另一个 Lua 版：

s = "s = %q\
print(string.format(s, s))"
print(string.format(s, s))

　　Scala ：

def e(s: String) = ("\"" + s.replace("\\", "\\\\").replace("\"", "\\\"") + "\"")
val s = "\"\"\"def e(s: String) = (\"\\\"\" + s.replace(\"\\\\\", \"\\\\\\\\\").replace(\"\\\"\", \"\\\\\\\"\") + \"\\\"\")\"\"\" + \"\\nval s = \" + e(s) + \"\\nprintln(\" + s + \")\""
println("""def e(s: String) = ("\"" + s.replace("\\", "\\\\").replace("\"", "\\\"") + "\"")""" + "\nval s = " + e(s) + "\nprintln(" + s + ")")

用某种方法 encode 源代码，使之不包含引号，然后还原出源代码

　　Bash ：

#!/bin/sh
s='\x22#!/bin/sh\ns=\x27$s\x27\necho $(echo -e $s)\x22'
echo "#!/bin/sh
s='$s'
echo $(echo -e $s)"

　　Lua 5.2 使用 load()：

s = "a,q,b=string.char(39),string.char(34),string.char(92) return a..'s = '..q..a..'..s..'..a..q..b..'nprint('..a..'..load(s)()..'..a..')'..a"
print('s = "'..s..'"\nprint('..load(s)()..')')

　　Scala ：

val s = "%22val+s+%3D+%5C%22%22+%2B+s+%2B+%22%5C%22%5Cnprintln%28%22+%2B+java.net.URLDecoder.decode%28s%2C+%22UTF-8%22%29+%2B+%22%29%22"
println("val s = \"" + s + "\"\nprintln(" + java.net.URLDecoder.decode(s, "UTF-8") + ")")

使用 eval ：在 eval 的字符串中引用自己

　　Lua load() 的另一种用法：

s = "print(string.format('s = %q load(s)()', s))" load(s)()

　　js 的 eval()：

s = "q = String.fromCharCode(34); console.log('s = ' + q + s + q + '; eval(s)')"; eval(s)

使用语言中的更强的转义机制

　　类似上面的第二种，但不用引号。

　　Lua 的 long string ：

x = [["x = [".."["..x.."]".."]\nprint("..x..")"]]
print("x = [".."["..x.."]".."]\nprint("..x..")")

　　Scala 的三引号：

val s = """"val s = \"\"\"" + s + "\"\"\"\nprintln(" + s + ")""""
println("val s = \"\"\"" + s + "\"\"\"\nprintln(" + s + ")")

使用 C 的宏

　　先执行传入的参数，再把参数变成字符串。

#define p(a) int main(){a;puts("p("#a")");return 0;}
p(puts("#define p(a) int main(){a;puts(\"p(\"#a\")\");return 0;}"))

　　至于它们是怎么实现的，就留给读者自己琢磨了。自产生程序也称为 Quine ，可以参考 Quine Page 。

评论邮箱评论帮助

请按照如下格式发邮件：
[email protected]
[复制]
评论 / 回复内容，只支持纯文本

这个问题早在7、8年前我就实现过，当时是参加夏令营，一个同学考我，就用Pascal实现了下。你的问题和所限定的要求不是很全，根据我以前的总结给你补充下。之所以不能用反射之类的手段，是因为我们要求所有的执行代码都必须输出，否则对C来说，头文件里声明一下main，编译单元里就直接打印“int main()”就是了。当然，把printf的代码也贴进来是无意义的，所以有一条要求是， 1、如果程序输出的观察者继续追究，我们的程序有能力把所有的实现代码都输出出来，包括标准库和汇编。当然读文件反编译就太简单了，所以还有一条要求是， 2、程序必须是platform-independent的，也就是说，代码拿过来，人脑一样可以跑一遍。以上两条要求只是为了增加严谨性，和可研究性。因为当时我做完这题后，还想要把一个自输出程序的模型抽象出来。不过当时太小了，花了一整个夏天都没搞定。（其实我当时根本就没深入理解什么叫做抽象……^_^）

henix2013-12-25[回复]

谢谢，我就是感觉自己对 cheating 的界定有些不清楚，虽然心里知道，但不知道该怎么表达...

xecle2013-12-11[回复]

我还以为是要讨论把程序本身从内存或硬盘上dump出来呢，像病毒那样克隆自己

noalac2013-04-22[回复]

当时用Perl实现得不完美，中间多输出一个反斜线，搞团队博客时又改了下 :) 看到这篇才发现原来还有这么多深层次的思考

此评论已被删除

Futurelancer2012-04-16[回复]

只需要制定演化规则，然后就可以让“生命”进化。规则可以是很简单的，但是经过足够时间，产生的“生命”可以足够复杂。

henix2012-04-20[回复]

话说你评论了之后我居然没收到邮件提醒。。。

Liufuqiang_robot2012-03-27[回复]