半遞歸集

半遞歸集(semi-recursive set)遞歸集概念的推廣.半遞歸集有兩種不同的涵義，在一般遞歸論中它指遞歸可枚舉集(re集);但在不可解度理論中，它通常指傑克什(Jockusch, C. G.)引進的如下概念:一集合A為半遞歸，是指存在二元遞歸函式f,使得.f (.x , y > -.x或.f(.},y>=y，並且.}EAVyEA=>f(二，戶EA.對後一涵義而言，遞歸集都是半遞歸集，且半遞歸集的補集也是半遞歸的.此外，半遞歸的reT完備集也是Q完備的.