标签：#遞歸論

不可解度

不可解度，或图灵度（Turing degree），是数学逻辑的名词，尤其应用在可计算性理论中。 定义 假设一个图灵机程序可以随意获取自然数函数g的值（即使g不可计算），且该图灵机计算自然数函数f，则定义函数f由函数g 图灵可计算，记作f\le_T g。符合以上特点的图灵机称为具备函数g的预言机。若集合B的特征函数可计算集合A，则A\le_T B。 在计算机科学和数理逻辑中，自然数集合的图灵度或者不可解度是对此集合的算法不可解性的度量。图…