补充资料：不可判定度

不可判定度
degree of undeddaUity

不可判定度【‘魄.锐of团吐劝‘城ty;.epa3pe山，。oeT。cTeueu‘」 自然数序列的子集上T叮初8归约性(:引进的一等价关系芝:(A兰:B，若A簇:B，且B簇:A).换言之，两集合有同一不可判定度，若对其中任一个集合有一能行的判定步骤，把任意数是否属于此集合的问题归约到另一集合的归属间题(亦见算法可归约性(algorithl如c阁ucibility)).不可判定度也可定义为处处有定义的函数(把自然数序列映射到它自身)的集合在相对递归性关系(;下的等价类.(一函数f相对于函数g是递归的(rec明i呢)，若f有一递归定义，在其中除了通常的初始函数外，g也作为初始函数出现).在此情形下，函数的不可判定度也称为不可计算度(deg找犯ofnon一comPutability);也称为该函数的T州ng度(T面Ilgdeg氏)或T度〔T，degee).对函数和集合的两种途径而言，所有不可判定度集组成一上半格(sen刀一httice)，且集合和函数的不可判定度的上半格同构.正是由于此而取这等价的定义. 不可判定度的上半格的结构已被详尽地研究(见!l]一[3])，这上半格的初等理论(elen℃ntary th印ry)是不可解的(【6」). 在不可判定度集上定义了一个跃变运算臼umP op-洲tion)，对每个不可判定度a赋予另一个度a几它是相对于“的递归可枚举不可判定度中最大的度.(集合B相对于集合A是递归可枚举的(recuxsively~ble)，若B是相对于A递归的集合的投影，且一不可判定度b称为相对于另一不可判定度a是递归可枚举的(卿珑i-祀ly enu汀坦mble)，若b包含一个相对于某A6a是递归可枚举的集合B.)跃变运算是单调的:a簇b蕴涵a’毛b’胆反向不成立).对每个不可判定度a)0‘有另一不可判定度b，使得a=b‘.不可判定度0间在算术集的甄和n。

说明：补充资料仅用于学习参考，请勿用于其它任何用途。