图灵归约

简称T归约。

设A，BN，如果B是A递归集，则称B可图灵归约到A，记作B≤A。如果A≤B且B≤A，则称A、B图灵等价，记作B≡A。

≤是自然数集上的自反、传递关系，≡是自然数集上的等价关系(自反、传递、对称)。

图灵归约≤和图灵等价≡有如下一些基本性质：

(1)．如果B≤A 则B≤A，如果B≡A 则B≡A；但反向的蕴涵式都不成立。

(2)．对任何集合AN，A≡A

(3)．如果A是递归集，则对任何B有A≤B

(4)．如果A是递归集，则B≡A当且仅当B是递归集。

自然数集在≡下的等价类称为图灵度(T度)。

(参见A递归集、m归约、图灵度)