可计算性理论的高级专题

递归定理

自引用

存在可计算函数$q:Σ^ → Σ^ $，对任意串$w,q(w)$是图灵机$P_w$的描述，$P_w$打印出$w$，然后停机。

递归定理 设$T$是计算函数$t:Σ^ ×Σ^ →Σ^ $的一个图灵机。则存在计算函数$r:Σ^ →Σ^* $的一个图灵机$R$，使得对每一个$w$ 有：$t(w)=t(,w)$

初看之下，此定理的叙述技术性很强，但实际上，它代表的事情很简单。为了制造一个能得到自己的描述、并用它计算的图灵机，只需要制造一个在上述定理中称为$T$的图灵机，使之以自己的描述作为输入的一部分。然后递归定理就产生一个新的机器$R$，它和$T$一样运行，只是$R$的描述被自动地装在$T$中。

递归定理的术语

递归定理指出图灵机可以输出自己的描述，然后还能用它继续进行计算。初一看，这个能力只是对一些无意义的任务有用，如制造一个打印它自己的备份的机器。实际上，递归定理是解决某些与箅法理论有关的问题的有力工具。

应用

函数的一个不动点（fixed point)是一个值，函数施加在该值上，得到的结果还是它。现在考虑图灵机描述的可计算的转换函数，对任意一个这样的转换，都存在一个图灵机，使得它的行为不随这个转换而改变。这个定理有时被称为 递归定理的不动点形式 。

逻辑理论的可判定性

转载请注明：转载自srzyhead的博客(https://srzyhead.github.io)

本文链接地址: 计算理论导引 (7-可计算性理论的高级专题)