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