自我打印程序和递归定理

对于自然语言，我们可以写出

照抄一遍这句话

如果你用自己的大脑去解释以上句子，并且用身体作为外部设备拿起纸笔重写出了 "照抄一遍这句话" ，那么你作为一台计算机器就执行了一个自打印程序。当然大部分人只是在大脑中模拟执行，在“心里”或想象中知道其结果还是 "照抄一遍这句话" ，这类似于大脑启动了一个终端模拟器，在虚拟终端执行了抄写或打印，而不是用物理上的打印机或纸笔。

也有可能大脑对 "这句话" 产生了困惑，于是抛出异常，感觉到本话题的无趣，从而关闭了当前页面。

如果把人类的大脑解释器替换成 ipython 解释器，那么以上句子在 ipython 交互式 shell 中对应的代码可能是：

print(get_ipython().user_ns['In'][-1])

print(get_ipython().user_ns['In'][-1])

这里 get_ipython().user_ns['In'][-1] 相当于 "这个句子", 它获取了当前交互式 shell 的最后一次用户输入内容，也就是“这句代码”，print 则等于“照抄一遍”。

关键在于 ipython 解释器提供了引用自身输入环境的接口 get_ipython()，如果要在更一般的 python 文件中引用到自身，则可以新建一个名为 self_print.py 的文件，其内容为：

with open(__file__, "r") as f:
     content = f.read()
     print(content)

执行 python self_print.py 后输出的是 self_print.py 里的内容。

以上源码对应的语义更接近于 “打印本文件的内容”。它之所以可行是因为 python 提供了现成的代词： "本文件" ，也就是预置的特殊变量 __file__ 。

文件层面的自引用代词还可以继续细分，比如由于 python 提供了 inspect.getsource 接口，可以在函数内通过函数名获取代码所在函数，而不是整个文件的源码，然后打印出来：

def print_my_self():
    import inspect
    # add any thing here
    source_code = inspect.getsource(print_my_self)
    function_name = print_my_self.__name__
    print(source_code)
    print("print_my_self()")

print_my_self()

def print_my_self():
    import inspect
    # add any thing here
    source_code = inspect.getsource(print_my_self)
    function_name = print_my_self.__name__
    print(source_code)
    print("print_my_self()")

print_my_self()

这些例子表明，python 中的行、函数，文件都可以被自引用，从而实现自我打印程序。在 python 交互式解释器中，数字则天然拥有打印自身的能力：

123

123

字符串则拥有近似的能力：

'self'

self

看了这么多的例子，不禁思考，程序或文本为什么会有“自我”的概念？

“我”的回答是：这是对日常中一般的“自我”概念的类比、泛化。

在代码中，”我“实际只是对程序中某一段区域的精确划分，如果在这段划分区域内部有代码能够“指出”当前划分区域本身，则被称为拥有“自指”或谈论“自我”的能力，这又引出了几个子问题：

1. “我”的边界如何确定？

   前文已经提到，整数、ipython 的交互输入行、 函数、文件都可以谈论“自己”，这些例子中，执行一段代码后，打印出了另一段完全一样的代码，从现象上看似乎“自打印”无可辩驳，但总是隐约带有点儿不踏实感。

   用一个例子来放大这种感觉，假设在 python 中实现了一个叫作 self_print 的打印函数：

   def self_print(s):
       if type(s) == str:
           return f"self_print('{s}')"
   

   那么将以上函数藏到内置库里，且把内置库、python 运行时、操作系统都排除在“自己”之外，就像把地面、空气和自然排除在“我”之外一样，那么只要是单引号输入的字符串都是自打印程序了，比如：

   self_print('你好 quine')
   

   self_print('你好 quine')
   

   这里的前提是只把以上代码块定义为“我”的管辖范围，并假装 self_print 具体的实现细节是环境的一部分，而不是“我”的一部分，但 self_print 的接口是“我”的一部分。如果把前文定义 self_print 的代码块也看作“自己”，它就不是自打印程序了。

   同样，在前文函数自打印的例子中，把 inspect.getsource 的调用代码看作“自我”，但它的定义则不是；在 ipython 自打印行的例子中，把 get_ipython() 的调用看作 "自我" ，但它的内部实现则被忽视，因为这些函数的定义被划分到了关注的区间之外。 我们只有假定某些底层机制是存在的，才能避免无限递归。否则你可以追问：既然整个程序执行涉及解释器， 那么自打印应该把整个解释器的源代码也都打印出来；但问题可以一直回溯下去：既然 print 是操作系统提供的，那么涉及 print 的自打印应该把整个操作系统也打印出来；既然操作系统需要硬件支持，那么自打印应该能自复制一台带 cpu 的主机，既然主机运行需要耗电，那么自复制计算机应该把电厂也复制，但既然电厂能量一部分来自于太阳能，那么应该重造太阳系，接着是银河系和整个宇宙。。。（原来这就是不踏实感的来源）

   因此，自打印程序中的“我”的边界需要明确规定，在一些场景中，自打印是显而易见的，比如 python 交互式解释器中的 123。 但另一些规定下，能否实现自打印并不明显，比如假设只能用 print 和几个字符串操作函数（见下一节）。

2. “我”一定是可以明确指出的吗？

   答：不是。

   前文刚定义过：如果在人为划分出的一段程序区域内部有代码能够“指出”这个划分区域本身，则被称为“自指”， 但这种“指出”并不一定是字面意义上有一个指向这段代码的 api，或 this 、 self 变量，它可以是隐式的 – 该区域中没有任何一个词提到 "这个", 但整个程序从行为结果上却是在表达或者操作自己。实际上 123 在 python 交互式解释器下就是这样的例子，但它过于简单，完全是人为提前设计的，因此并不有趣。

   一种回到日常生活的类比是，一个人完全不需要谈论“我”、”笔者“、”在下“等明确指代自己的词， 也不需要用手指指着自己宣布自身的存在，只需要以某一种姿态存活着就是在展现自身。

   这是后文讨论的核心，即程序如何能够做到不提及“我”而表达或操作“我”， 具体来说，是用一种编程技巧（trick）构造性地进行证明，即写出不调用表示 “这个”的 api 的自打印程序。

3. 前文例子中，inspect.getsource, get_ipython 等明确的访问程序自身的 api 是因为计算机更底层的什么性质而得以实现的？

   这里不去讨论具体的细节，这些接口之所以可能，本质上是因为代码就是一段数据，而现代计算机是基于寄存器加内存随机寻址机制的 RAM 机，得益于数字电路的设计，单个 bit 锁存器中保持的信号（可被视为静态的数据）可以作为其他门电路的输入去控制数字电路的行为（可被视为动态的代码）; 在多个 bit 组成的寄存器层面，给定一个地址， CPU 可以解码它并访问到地址中的其他数据；在 C 层面，这种能力被封装成了指针；操作系统层面维持着程序的初始地址信息； python 层面的这些接口最终都是请求操作系统返回特定数据，只不过这些数据恰好是要执行的程序本身。 （注：因为安全考量，一些实际应用中，程序的运行环境不允许访问本地文件，比如浏览器的 javascript 环境，甚至会故意把程序加载的位置随机设置，以增加黑客程序的攻击难度）

4. “我”就是程序源代码吗？

   答：不是。

   程序在计算机里有多种表征形态，比如 utf-8 形式的源代码，也有解析后的抽象表示，如解析树，抽象语法树，字节码，汇编，二进制码等等，以上讨论的“自己”只是外表上的源代码。实际在各个抽象层级，只要能逻辑上划分出区域（比如函数，变量，类），那么就能够逻辑地在这些区域内部引用到区域自身，最后一章会有讨论。

总之，计算机科学家们发现，在划分出的“我”的代码区域中即便不能直接提供访问程序表征的 api, 但只要有一般编程预压所具备的基础功能，比如有打印和读取纸带或“内存”的语法，操作字符串的 string 库等，就可以实现引用到自身的程序。

这意味着如果操作系统不配合或者压根没有操作系统（比如是想象中的非数字电路机器），程序还是可以访问到自身表征， 自打印是这种能力的源代码层面的体现，它肤浅却又深刻。肤浅在于它仅仅是关注程序的外表以及这只是一种几乎没有实际用处的编程技巧，时常伴随着神秘感以及强烈的个人自我的展现欲（这可能和上世纪计算机发展早期几十年里黑客、反叛精神、开源文化有关，比如 GNU 这种自指缩写文字游戏）；深刻在于它蕴含了一种理论层面的否定性质的观点，是哥德尔不完备定理，停机问题的延伸（见后文递归定理一节），表明有些看似清晰定义的需求是不可能实现的，因此这又是对膨胀的人类理性自我的一种约束（也许这种你无法逃出逻辑自身的压制对戏谑的黑客精神有一定促进作用，比如银河系漫游指南的态度 – 别在寻找终极答案的漫游中无限递归了，它就等于 42。）

在 计算理论导引（原书第3版） 6.1 节中，基于图灵机模型描述了如何实现自打印的机器，方便起见，本节基于一种想象中的使用 python 风格打印语句的“机器”，它有一个可以读取和写入的一维纸带，称为内存，这片内存能够直接映射到屏幕，在该机器上执行 print(x) 会把 x 内容写入这片内存，并且显示在显示器上，故称为“打印”。

为了实现打印自身的程序，可以采取一种分治的思路，把执行过程拆成 A 和 B 两部分，相应地，程序源码由 <A><B> 两部分拼接而成（添加尖括号表示这是程序的源码），我们期望：

• 执行完 A 部分后 <B> 会出现在内存上。所以 A 应该 print(<B>) 类型的程序（或者某段能够生成字符串 <B> 的算法），也就是说 A 程序依赖 <B> 的内容。
• 由于执行完 A 部分后，内存上有了 <B> ，为了使得最终内存里内容是 <A><B>, B 就需要在当前内存内容 <B> 的前面插入 A 的代码。因此 B 程序需要知道 A 是什么。

问题来了，A 需要知道 B 的内容，而 B 为了插入 A 的代码需要知道 A，这不就无限踢皮球了吗？

关键是，B 可以不用提前知道 A 的代码，而是通过 A 程序打印的 <B> 逆向推测出 A 本身，这看上去就像观察某个鸡蛋就能推测下蛋的母鸡是什么样子一样神秘而复杂，但其实当你看到 python 的交互终端屏幕上出现 123 的时候，很容易反推出一个正确的程序： print(123) ，当然 print("123") 或者 print(100+20+3) 也是正确的：

>>> print(123)
123
>>> print("123")
123
>>> print(100+20+3)
123

所以看似无限递归但却不是的原因在于这台机器打印的机制 print 是固定的，并且它的实现细节被排除在 "自我" 之外，否则会险入第一章提到的复制银河系和宇宙的问题。B 程序清楚这种固定的打印机制就是递归终点了，从而可以在见到数据后反推出打印数据的程序。

而 B 反推出的打印机制（比如只是给它读到的数据加一个 print）要和 A 真正实现的打印机制保持一致（由于打印某个字符串的程序有无限可能，比如以上 123 列出了至少三种打印方式，因此可以写出无限多自打印程序）。

更一般地，当进入 B 段的时候，A 段已经执行完并在内存上留下一堆数据 data ，B 知道原来 A 是一个打印了这一堆数据的程序。如果 B 能够根据内存数据而逆向破解出打印这些数据的程序，就可以在内存开头插入程序 <A>。 这样机器运行结束之后，内存上就留下了 <A>data, 如果 A 留下的是 <B>, 最终结果就是 <A><B>

而 B 实现的是根据数据而逆向合成打印数据的代码并把这段代码插入到内存最前面的功能， 这是一种通用的字符串数据分析和生成机制，或者说是数据驱动的程序合成，它和具体的数据无关，因此不依赖于 A。所以我们可以写出程序 <B> ，而 <A> 则是类似 print(<B>) 的打印程序。

因此实现的思路是这样的：

• 先写出一个程序，它能够读取某个片内存里的字符串，用 data 指代（关键这是一个字符串类型的占位符, 与具体数据无关），根据 data 生成一段打印 data 的程序 – 也是字符串，比如是 print(data), 它操作这片内存，把 print(data) 移动到现有的内存数据前面，使得内存最终为 print(data)data. 这个程序的代码记为 <B>, 其代码中不包括具体的内存数据 data, 而只包含对任意潜在数据的操作机制。
• A 的实现是 print(<B>)
• 最终自打印程序是 print(<B>)<B>

所以这里的需要的最少功能有哪些？

• 能够读取内存字符串
• 能够拼接字符串
• 能够移动内存数据并且写入内存

也就是一般字符串操作库中的一小部分。

如何把前文在自定义模型上描述的拆分成 <A><B> 两部分的思路迁移到 python 呢？

首先，python 中 print(<B>) 会把字符串 <B> 打印到屏幕，其他程序无法从标准输出把 <B> “读取”回来再进行数据分析。因此 python 里能读能写的不是屏幕，而只能是内存，更具体的，由于 python 是高层语言，内存是通过变量来引用的，比如 tape=<B>, 而这个操作可以看作是“打印” – 往可读可写的区域写入内容，其他程序又能用引用 tape 从而获得当前打印的内容，比如移动其中的字符串顺序、把字符串真正显示到屏幕等。

其次，python 的内存里保存的数据和屏幕显示的数据可能会不一致，比如转义字符，而上节中假设内存中显示的和人们看到的“打印”结果一致，这在之后具体实现中会遇到并解决。

要用 python 写出 B 程序，需要先从 tape 变量中获得数据，然后反推出一个打印 tape 里数据的程序所对应的字符串（也就是加上 tape= 前缀），因此这涉及字符串格式化，用 fstring 或一般字符串拼接都可以。

具体实现思路如下：

通过 fstring 里的 {tape} 就能获得内存里的数据，而这种数据是 A 通过 tape="…" 赋值（也称打印）语句得到的，于是 B 推测出 A 就是 f"tape={tape};" 形式的程序，注意第二个 tape 是 B 看到的内存数据的“指代”，B 不需要知道那里面是什么，第一个 tape 以及其他的符号是把这些数据打印到内存所需要的相关指令。

这还不够，B 还要把它推测出的 A 程序的代码放在当前内存区域之前，当前内存区域是什么呢？也就是 {tape}, 所以 B 应该是 f"tape={tape};{tape}" 形式的，而 A 要把 B 打印，于是用这部分内容去替换 A 里的 … ，那么 A 就应该是：

tape="f'tape={tape};{tape}'";

注意这里要考虑单双引号问题，和 B 拼接：

tape="f'tape={tape};{tape}'";f"tape={tape};{tape}"

tape=f'tape={tape};{tape}';f'tape={tape};{tape}'

可以看到这非常接近了，AB 形式自打印程序的思想核心已经被实现，只是打印结果少了双引号，可以把注意力转向 python 对字符串和字符串打印的设计细节问题。

为什么会丢失双引号？因为 B 程序中 tape={tape} 是把内存里的内容放在 tape= 字符串之后，但这段内容实际应该被 quote 起来（引用括起来），一种朴素尝试是直接在 {tape} 两端添加括号，这里需要添加单引号：

tape="f'tape='{tape}';{tape}'";f"tape='{tape}';{tape}"

tape='f'tape='{tape}';{tape}'';f'tape='{tape}';{tape}'

以上打印的结果不是一个符合语法的 python 程序，因为第一个 tape= 后嵌套了太多单括号了

tape='f'tape='{tape}';{tape}'';f'tape='{tape}';{tape}'

  Cell In[21], line 1
    tape='f'tape='{tape}';{tape}'';f'tape='{tape}';{tape}'
            ^
SyntaxError: invalid syntax

所以我们需要一种不通过添加字面量引号的添加引号的方式，这里用 repr

tape="f'tape={repr(tape)};{tape}'";f"tape={repr(tape)};{tape}"

tape="f'tape={repr(tape)};{tape}'";f'tape={repr(tape)};{tape}'

以上程序并不是完美的自复制，因为最后一个 fstring 是单引号而不是源代码里的双引号，但实际它们的语义是完全一样的，而且将打印的结果程序再执行一遍就能得到真正的自打印 程序，也就是说这个程序打印出了一个和自己非常像的自打印程序，而不是打印出了自己。

把以上结果复制到代码框里执行：

tape="f'tape={repr(tape)};{tape}'";f'tape={repr(tape)};{tape}'

tape="f'tape={repr(tape)};{tape}'";f'tape={repr(tape)};{tape}'

这确实是一个真正的自打印程序。

可以不借助 repr, 而是底层 ascii 来添加引号

tape="f'tape={chr(34)+tape+chr(34)};{tape}'";f'tape={chr(34)+tape+chr(34)};{tape}'

tape="f'tape={chr(34)+tape+chr(34)};{tape}'";f'tape={chr(34)+tape+chr(34)};{tape}'

可以随意加花：

tape="f'tape={chr(30+4)+tape+chr(38-4)};{tape}'";f'tape={chr(30+4)+tape+chr(38-4)};{tape}'

tape="f'tape={chr(30+4)+tape+chr(38-4)};{tape}'";f'tape={chr(30+4)+tape+chr(38-4)};{tape}'

了解了 AB 形式打印程序的思路，并且成功写出一个 demo 之后，就可以尝试在这个框架下实现满足其他偏好的自打印程序了

假设我们希望在 A 中塞入任意多信息，比如希望这段程序里包含 "a python self print program", 类似一个签名，如何添加？

一种做法是，把这些信息编码到 x 变量名，比如把 x 改成 a_python_self_print_program, 但这像是一种脑筋急转弯，如果其中包含 ? 或其他变量名中不被允许的符号就失效了。

我们先约定额外的数据是被 A 生成的，并且放在其打印的数据的最后，当 B 看到了内存区域并知道 A 要携带多少额外的内容后，它可以把 A 程序放到 A 生成的数据 <B> 的前面， 并且按长度截断 A 生成的额外数据的部分：

x="print(f'x={repr(x)}');x[:-10]1234567890"
print(f'x={repr(x)}');x[:-10]

x="print(f'x={repr(x)}');x[:-10]1234567890"
print(f'x={repr(x)}');x[:-10]

如果 x 的内容里都没有空格，也可以用空格作为分隔符去携带信息，此时信息里最好不要有空格：

x="print(f'x={repr(x)}');'_'.join(x.split()[:-1]) a_python_self_print_program"
print(f'x={repr(x)}');'_'.join(x.split()[:-1])

x="print(f'x={repr(x)}');'_'.join(x.split()[:-1]) a_python_self_print_program"
print(f'x={repr(x)}');'_'.join(x.split()[:-1])

前面实现的都是以下形式的 AB 形式的自打印程序：

"将以上句子打印两遍，第一遍用引号括起来"
将以上句子打印两遍，第一遍用引号括起来

A 是被动的数据部分，B 是主动的指令部分

如果把代词替换成“以下”则变成：

将以下句子打印两遍，第二遍用引号括起来
"将以下句子打印两遍，第二遍用引号括起来"

主动的用于代码合成的 B 部分被放在了前面，这对于自然语言写起来很简单，但 python 不支持先引用后定义，以下会报错。

print('tape=' + repr(tape) + tape);tape=";print('tape=' + repr(tape) + tape)"

我们必须把 A 完全作为数据（即不需要 tape= 这种写入指令），直接喂给 B, 而只有函数才能直接获得数据，因此 B 应该是一个单变量函数，但它不能是原生的 print 函数：

print(2*"print(2*")

print(2*print(2*

因为我们丢失了对 tape 的引用，很难去操作 tape 内存里的数据，比如把推测出的程序插入到已有数据之前，以上只能用很原始的 2* 方式去对输入内容做复制，但细节的控制完全丢失，因此无法写出自复制程序 （如果你能不借助函数变量写出自复制程序，请告知我）。

所以需要用一个 lambda 函数去包装，这里函数参数 x 作为 tape 内存的引用，由于 A 部分在 B 之后，那么 repr 就应该放在第二个 x 上：

(lambda x: print(x+repr(x)))("...")

用 B 部分 （lambda 函数）替换 … ：

(lambda x: print(x+repr(x)))("(lambda x: print(x+repr(x)))")

(lambda x: print(x+repr(x)))'(lambda x: print(x+repr(x)))'

这里 (lambda ..)() 之后的调用括号不见了，原因在于以上不是严格的 BA 形式，而是 B(A) 形式，A 的两侧是有括号的，因此加上去：

(lambda x: print(x+'('+repr(x)+')'))("(lambda x: print(x+'('+repr(x)+')'))")

(lambda x: print(x+'('+repr(x)+')'))("(lambda x: print(x+'('+repr(x)+')'))")

得到了正确的自打印程序

现在我们考虑如何能用其他技巧来避免手动添加两个字符串括号，因为这看上去很乱，由于 python tuple 也是用括号来保存数据的，比如 (1,2) 和 f(1,2) ，前者是 tuple, 而后者是函数调用，但是 (1) 会被解释成 1:

(1)

1

所以不能用 (x) 来表示出 f(x) 中的后半部分，而是用 (x,) ，而 python 里，可以支持 f(x,) 这样的调用：

print(1,)

1

所以可以用以下方式

(lambda x: print(x+str((x,))))('(lambda x: print(x+str((x,))))',)

(lambda x: print(x+str((x,))))('(lambda x: print(x+str((x,))))',)

或者：

(lambda x: print(x+repr((x,))))('(lambda x: print(x+repr((x,))))')

(lambda x: print(x+repr((x,))))('(lambda x: print(x+repr((x,))))',)

然而，既然函数调用已经写成 f(x,) 形式了，那么再加一个 python 中的字面量作为参数也是可以的：

(lambda x,y: print(x+str((x,y))))('(lambda x,y: print(x+str((x,y))))', 1)

(lambda x,y: print(x+str((x,y))))('(lambda x,y: print(x+str((x,y))))', 1)

这种情况下，程序变成了 B(A,D) 形式，A,D 先运行，A 把 <B> 放到 x 内存区，D 把数据放到 y 内存区，而 B 通过 lambda x,y 的形式，同时可以获得两条纸带并操作它们，先用 str((x,y)) 把 (A,D) 复原，然后把 x ，也就是 <B> 放到它们之前：

(lambda x,y: x+str((x,y)))('(lambda x,y: x+str((x,y)))', 1)

(lambda x,y: x+str((x,y)))('(lambda x,y: x+str((x,y)))', 1)

这里第二个参数可以携带任意字符串数据（打印结果就是字面量的数据）：

(lambda x,y: print(x+str((x,y))))('(lambda x,y: print(x+str((x,y))))', 'this is a self print function')

(lambda x,y: print(x+str((x,y))))('(lambda x,y: print(x+str((x,y))))', 'this is a self print function')

当然更多参数也是可行的

(lambda x,y,z: print(x+str((x,y,z))))('(lambda x,y,z: print(x+str((x,y,z))))', '1', (1, 2))

(lambda x,y,z: print(x+str((x,y,z))))('(lambda x,y,z: print(x+str((x,y,z))))', '1', (1, 2))

这和前文提到的在自复制中携带任意静态数据不同，我们希望可以在自打印程序中添加额外的代码而不是数据，执行该程序之后，它不单打印出了自身，还可以额外的做其他任何操作，比如播放音乐（如果该语言能有这个功能），关机（如果它有权限），或者继续对自身代码做额外操作 – 保存在其他文件里，把自身代码打印两份等等。

这里的思路和构造 AB 型自打印程序是类似的，但由于要做额外的事情，那么需要提供一个新的部分 T, 它会读取内存里的数据并对其进行操作，把 T 拼接到 AB 的后面，因此完整的程序是 ABT 三部分组成的形式：

• A 的作用是打印出 <B><T>
• B 的作用是根据当前内存区里的内容构造出 A 程序的内容，并且把 <A> 放到 <B><T> 之前
• 此时 T 看到的内存包括 <A><B><T>, 它可以对它做任何事情，这和设计的意图有关。

根据这个思路，假设 T 是读取并打印内存里内容的长度，那么它的实现就是：

print(len(x))

接着 B 是推测出 A 程序并把它放在已有内存数据之前，注意此时 B 需要真正修改内存区，再将其打印：

x=f'x={repr(x)};{x}';print(x)

A 是以上二者的拼接

x="x=f'x={repr(x)};{x}';print(x);print(len(x))"

最终就是：

x="x=f'x={repr(x)};{x}';print(x);print(len(x))";x=f'x={repr(x)};{x}';print(x);print(len(x))

x="x=f'x={repr(x)};{x}';print(x);print(len(x))";x=f'x={repr(x)};{x}';print(x);print(len(x))
91

这段程序打印出了自身并打印出了自身字符的数量。

以上自打印部分不是必须的，因此 B 部分的代码可以简写成：

x=f'x={repr(x)};{x}'

如果需要自打印，可以把 T 设计成： print(x), 于是得到另一种自打印程序：

x="x=f'x={repr(x)};{x}';print(x)";x=f'x={repr(x)};{x}';print(x)

x="x=f'x={repr(x)};{x}';print(x)";x=f'x={repr(x)};{x}';print(x)

这个过程可以推广，把程序拆分成 ABC…T 其中 C 部分到 T 部分之前（不包含 T 部分）只要保证内存区内容不被修改，那么自打印程序可以无限长，比如简单的重复 x:

x="x=f'x={repr(x)};{x}';x;x;x;print(x)";x=f'x={repr(x)};{x}';x;x;x;print(x)

x="x=f'x={repr(x)};{x}';x;x;x;print(x)";x=f'x={repr(x)};{x}';x;x;x;print(x)

这意味着可以在其中塞入任何“签名”

x="x=f'x={repr(x)};{x}';'I am self print';print(x)";x=f'x={repr(x)};{x}';'I am self print';print(x)

x="x=f'x={repr(x)};{x}';'I am self print';print(x)";x=f'x={repr(x)};{x}';'I am self print';print(x)

最后再设计一个打印程序中包括多少个 = 符号的程序， T 部分是

print(x.count('='))

BT 就是

x=f'x={repr(x)};{x}';print(x.count('='))

ABT 则是

x="x=f'x={repr(x)};{x}';print(x.count('='))";x=f'x={repr(x)};{x}';print(x.count('='))

7

注意这里把 count('=') 里的 = 也统计进去了

统计有多少 print

x="x=f'x={repr(x)};{x}';print(x.count('print'))";x=f'x={repr(x)};{x}';print(x.count('print'))

4

无限执行自身（栈溢出，如果放在操作系统环境下，绕过执行环境的栈限制就可以称为病毒了）：

x="x=f'x={repr(x)};{x}';exec(x)";x=f'x={repr(x)};{x}';exec(x)

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
Cell In[106], line 1
----> 1 x="x=f'x={repr(x)};{x}';exec(x)";x=f'x={repr(x)};{x}';exec(x)

File <string>:1

File <string>:1

    [... skipping similar frames: <module> at line 1 (2974 times)]

File <string>:1

RecursionError: maximum recursion depth exceeded

写成两行：

x="x=f'x={repr(x)+chr(10)+x}';exec(x)"
x=f'x={repr(x)+chr(10)+x}';exec(x)

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
Cell In[16], line 2
      1 x="x=f'x={repr(x)+chr(10)+x}';exec(x)"
----> 2 x=f'x={repr(x)+chr(10)+x}';exec(x)

File <string>:2

File <string>:2

    [... skipping similar frames: <module> at line 2 (2974 times)]

File <string>:2

RecursionError: maximum recursion depth exceeded

BA 形式可以有更方便的写法，它可以把执行部分 T 放到 B 内部，因为 B 是一个 lambda 函数，它要操作的内存就是其参数 x:

单参数：

(lambda x: len(x+'('+repr(x)+')'))("(lambda x: len(x+'('+repr(x)+')'))")

72

双参数：

(lambda x,y: len(x+str((x,y))))('(lambda x,y: len(x+str((x,y))))', '1')

71

BA 形式双参数统计 "lambda" 的出现次数：

(lambda x,y: (x+str((x,y))).count("lambda"))('(lambda x,y: (x+str((x,y))).count("lambda"))', '1')

4

BA 形式无限执行自己：

(lambda x,y: exec(x+str((x,y))))('(lambda x,y: exec(x+str((x,y))))', '1')

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
Cell In[27], line 1
----> 1 (lambda x,y: exec(x+str((x,y))))('(lambda x,y: exec(x+str((x,y))))', '1')

Cell In[27], line 1, in <lambda>(x, y)
----> 1 (lambda x,y: exec(x+str((x,y))))('(lambda x,y: exec(x+str((x,y))))', '1')

File <string>:1

File <string>:1, in <lambda>(x, y)

File <string>:1

    [... skipping similar frames: <lambda> at line 1 (1486 times), <module> at line 1 (1485 times)]

File <string>:1

File <string>:1, in <lambda>(x, y)

RecursionError: maximum recursion depth exceeded

以上所有的例子实际展示的是递归定理（克莱尼第二递归定理），它的一种描述是：

如果你实现了任何一个处理字符串的程序 f(s) ，比如打印字符串 s 、统计 s 中某子串个数、把 s 当作程序进行编译，那么我一定可以写出某个程序 g, 执行 g() 等价于执行 f(<g>) 。

也就是可以实现一个程序 g, 它可以获得自身的源代码，并且基于自身源码做任何可以实现的操作。 自打印程序、统计子串个数、不断执行自身（病毒）的程序是几个特定的案例。

从更抽象的层面上说，在图灵机或图灵等价的机器上，一定可以实现能够看到自己源代码并对其进行任意可计算操作的程序。

这个定理有什么用呢？实际上它的意义更多来自否定层面：

• 实践中，这种程序非常少见，即便真的有这种需求，那么也可以使用前文提到的向操作系统申请来获取源代码的方式， 但能够获得源文件或者程序加载地址容易产生安全问题，因此很多程序会限制这种能力，比如浏览器中的 js 运行环境。

• 在理论上，它更多也是用来证明一些不可能的性质，比如可以用它精简地说明停机问题：如果存在一个程序 h(s)，它能够接受其他程序的源代码，判断它是否停机，那么可以编写一个程序 f(s), 它调用 h(s), 如果 s 执行后会停机，那么运行一个无限的 while 循环使得自身不停机，否则马上返回。

  那么根据以上定理，存在机器 g, 它能获取自己的源代码 g, 并且模拟 f(<g>) 的功能，如果 <g> 停机，g 就不停机，否则 <g> 停机，导致了逻辑矛盾，而逻辑矛盾被认为是“更高”的否决准则， 因此它否定了这种程序物理的存在性。