相對可計算性

相對可計算性(relative computability)可計算性概念的推廣.若在給定一個集合A的信息後，就可能行地計算一個部分函式f或集合B的特徵函式，則稱f或B是相對於A可計算的.

相對可計算性(relative computability)可計算性概念的推廣.若在給定一個集合A的信息後，就可能行地計算一個部分函式f或集合B的特徵函式，則稱f或B是相對於A可計算的.正如T可計算性很好地刻畫了直觀可計算性一樣，相對可計算性也可以用帶外部信息源的圖靈機進行刻畫.即如果一個部分遞歸函式f可由一帶有外部信息源A圖靈機進行計算(}e(.f=}e ))，則稱f相對於A可計算.若集合B的特徵函式相對於A可計算，則稱B相對於A可計算(記為B鎮TA)，亦稱B是A可計算的.這樣一來，B是A可計算與BT可化歸到A實際上是一致的.
一個部分遞歸函式f相對A可計算，若且唯若f相對部分遞歸於A一集合B相對於A可計算，若且唯若B遞歸於A(參見“帶外部信息源的圖靈機”，“相對部分遞歸性”).