不可解度
不可解度,或图灵度,是数学逻辑的名词,尤其应用在可计算性理论中。
假设一个图灵机进程可以随意获取自然数函数的值(即使
不可计算),且该图灵机计算自然数函数
,则定义函数
由函数
图灵可计算,记作
。符合以上特点的图灵机称为具备函数
的预言机。若集合
的特征函数可计算集合
,则
。
在计算机科学和数理逻辑中,自然数集合的图灵度或者不可解度是对此集合的算法不可解性的度量。图灵度在可计算理论中是根本性的概念,在可计算理论里,自然数集合通常被看作一个判定问题,而图灵度则给出了解决与此集合相连的判定问题的困难程度。
如果两集合有同一不可解度(也即两者互相图灵可计算),则称两集合为图灵等价,记作
。图灵等价是一个等价关系,其等价类称作不可解度。图灵可计算关系是所有不可解度的搜集上的偏序。所有可计算集合(也即图灵等价于空集的集合)的不可解度为
(零度)。