不可解度

维基百科,自由的百科全书
跳转至: 导航搜索

不可解度数学逻辑名词函数f由函数g图灵可计算,并且gf图灵可计算时,称fg具有相同的图灵不可解性的度。

在计算机科学和数理逻辑中,自然数集合的图灵度或者不可解度是对此集合的算法不可解性的度量。图灵度在可计算理论中是根本性的概念,在可计算理论里,自然数集合通常被看作一个判定问题,而图灵度则给出了解决与此集合相连的判定问题的困难程度。

两个集合是图灵等价的,如果这两集合有同一不可解度,每一个图灵度是一些图灵等价的集合构成的搜集(类),因此两个集合如果不是图灵等价的,那么就属于两个图灵度。更进一步,图灵度构成一个偏序。