3,094
个编辑
更改
跳到导航
跳到搜索
第264行：
第264行： − + + + + + + +
→直观图景：程序如何"谈论"自己的代码
=== 直观图景：程序如何"谈论"自己的代码 ===
=== 直观图景：程序如何"谈论"自己的代码 ===
'''例 1（Quine，Python 版）'''〔示例取自 Wikipedia "Quine (computing)"<ref name="wikipedia_quine_computing">'''Wikipedia.''' ''Quine (computing)''. <https://en.wikipedia.org/wiki/Quine_(computing)>. 【quine的准确定义：不接受输入、只输出自身源码、且不得读取自身源码】【§[[#Quine（自打印程序）|5.7.6]]】</ref>；与 SRT 的关系见 Kiselyov<ref name="kiselyov"/>, §2〕：所谓 '''quine''' 就是"打印出自己源代码的程序"。第二递归定理断言：这样的程序必然存在。下面这个 Python 程序就是教科书级的 quine——运行它，会原样打印出它自己的源码：
递归函数即可计算函数。然而，我们接触到的大部分程序都是使用字符串来编码，而并非使用自然数。这就使得初学者会对函数或程序的编码非常困惑，而第二递归定理（SRT）本身就是建立在两套编码对应的函数功能等价的基础之上的，因此造成很多的理解困惑。
实际上，一个递归函数，或可计算的图灵机程序，既可以被编码为自然数，又可以被编码为字符串，也就是源程序代码，二者本质上等价。要建立这种等价关系，我们只需要按照字典序为所有可能的字符串做自然数编码就可以了，于是任何一个字符串都对应了一个自然数，反之自然数也可以对应回字符串。这样，所有关于SRT的结论都自然能够平移到我们熟悉的以字符串对应函数编码的程序世界里。
程序世界里SRT的一个最简单的对应物就是[[Quine程序]]，即“打印自己源代码”的程序。
'''例 1（[[Quine]]，Python 版）'''〔示例取自 Wikipedia "Quine (computing)"<ref name="wikipedia_quine_computing">'''Wikipedia.''' ''Quine (computing)''. <https://en.wikipedia.org/wiki/Quine_(computing)>. 【quine的准确定义：不接受输入、只输出自身源码、且不得读取自身源码】【§[[#Quine（自打印程序）|5.7.6]]】</ref>；与 SRT 的关系见 Kiselyov<ref name="kiselyov"/>, §2〕：所谓 '''quine''' 就是"打印出自己源代码的程序"。第二递归定理断言：这样的程序必然存在。下面这个 Python 程序就是教科书级的 quine——运行它，会原样打印出它自己的源码：
<syntaxhighlight lang="python3">
<syntaxhighlight lang="python3">