递归定理

阐述

存在一个可计算函数，将字符串 $w$ 映射为一个 Turing 机 $P_w$ ，它能输出字符串 $w$ 。

分为两部分 $A=P_{\langle B\rangle}$ 和 $B$ （对于每个输入 $\langle M\rangle$ ，计算 $q(\langle M\rangle)$ 并把这个 Turing 机和 $M$ 合在一起输出。

若 $T$ 是能够计算函数 $t:\Sigma^*\times\Sigma^*\to\Sigma^*$ 的 Turing 机，则存在一个 Turing 机 $R$ 且对于每个输入 $w$ ，都有

r(w)=t(\langle R\rangle, w)

设 $t:\Sigma^*\to\Sigma^*$ 是一个可计算函数，则存在一个 Turing 机 $F$ 使得 $t(\langle F\rangle)$ 是一个与 $F$ 等价的 Turing 机。

它可以用于证明下列语言不是 T-可识别的：

M I N_{\mathrm{TM}}=\{\langle M\rangle \mid M \text { is a minimal TM }\}