可化歸性

可化歸性（reducibility），遞歸論術語，指反映函式之間可計算性相對難易程度的一個概念。

直觀地說，如果在使用了函式f的信息後，就可以能行地計算另一個函式g，則稱g可化歸到f(記為g},-f,).如果自然數集合A的特徵函式可化歸到自然數集合B的特徵函式，則稱A可化歸到B(記為A蕊,B).對此直觀概念的不同的形式化便定義出相應的嚴格的化歸概念.如真值表化歸，圖靈化歸等.雖然這些化歸有許多不同的特性，但它們也有以下一些共同點.首先，可化歸關係都具有自反性與可傳，因此由可化歸關係G:可導出等價關係“三:"(A=:篤了AG,B八BG,A>.其次，任何可化歸到遞歸集集合都是遞歸集，並且在大部分情況下(除一一化歸和多一化歸)，遞歸集可化歸到任何集合，這表明，在化歸關係“蕊r”之下，遞歸集是最“小”的，這正好反映了遞歸集具有最低的不可解程度.此外，所有可化歸關係還具有遞歸不變性，即若A,B遞歸同構則A三:B.如果蕊r1 ,毛r2是兩種化歸關係，則若對任何集合A,B，都有A毛r1B->A毛,2 B，便稱毛r,比毛"Z強·