不可判定的遞歸論問題

不可判定的遞歸論問題(undecidable problemsin recursion theory)是指已被證明不具有可判定性的一類遞歸論問題。

遞歸論本身的大部分問題都是不可判定的.其中最基本的問題是停機問題(參見“停機問題”).除此之外，根據瑞斯(Rice,H. G.)定理，任何非平凡(即不等於必，動的下標集A(即存在部分可計算函式的類“了，使A={e:}peE}})都是非遞歸的，因此，大部分涉及下標的遞歸論問題都是不可判定的.常見的有:
判定件與}y是否相等?
判定W二是否有窮?
判定W二是否為遞歸集?
判定W二是否為空集?
判定}s是否為全函式?