不可解度【英】

degree of unsolvability

译文来源

[1] 金炳华，冯契.哲学大辞典[Z].上海辞书出版社，2001：119.
[2] Degrees of Unsolvability. via: http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf

定义

“递归论重要概念之一。指递归不可解的程度。在研究判定问题时，人们发现，不同的不可解的判定问题之间，不可解的程度有差别。已有几种方法去刻画这种不可解度。通常使用的是图灵（不可解）度。图灵度概念是建立在相对递归或相对可计算概念之上的。通常称部分函数f相对于部分函数g是递归的，若f由初始函数与g出发经有限次使用标准迭置、原始递归式和μ算子而得，则记为f≤Tg。由于任何判定问题通过适当的编码技术，都可化为如“x在A中么？”（A为N的某子集）这样的问题，因此任何一个判定问题都与N的某个子集有关。于是比较判定问题的不可解的程度可以归结为比较N的各个子集之间的某种关系。设N的两个子集A与B。称A图灵可化归于B，若函数CA递归于函数CB，记为A≤TB。若A≤TB，且B≤TA ，则称A与B是图灵等价的，记为A≡TB。可以证明关系“≡T”是一个等价关系。故按“≡T”可把N的所有子集加以分类，而每个等价类称为一个图灵度。具体地说，令A⊆N，则含有A的等价类dT（A）=｛B｜B≡TA｝称为A的图灵度，或简称为A的T度。从直观上看，若A≤TB，则相对于B的判定问题（即x∈B？）的不可解的程度不低于A的判定问题的不可解的程度。若A≡TB，则相对于A与B的两个判定问题的不可解性程度同样高。若A≤TB，但A≢TB（即B≰TA），记为A

定义来源

金炳华，冯契.哲学大辞典[Z].上海辞书出版社，2001.

网络参考例句

例句 1：
其中涉及如下与复杂性有关的逻辑与认识论问题：（1）计算复杂性特别是不可解度等内容；（2）概念等级序列在内的逻辑完备性问题；（3）不同解释模型比较的模型论问题。——“复杂性科学研究中的两个哲学问题思考”，载于《哲学动态》2007年第9期