不可判定的问题
书籍:逻辑百科辞典
不能用一个能行过程确定任给的一对象是否具有某一性质或属于某个类的问题(参见判定问题)。
以下是文献中常提到的一些不可判定问题的例子：
1．停机问题：“第x号图灵机在输入自然数y之后能停机”(可表示为“y∈W”或“φ(y)有定义”)是不可判定的(但仍是半可判定的)。
2．“φ是全函数”是不可判定的(此问题及其否定问题都不是半可判定的)。
3．“φ=φ”是不可判定的(此问题及其否定问题都不是半可判定的)。
4．一阶谓词逻辑系统是不可判定的(但仍是半可判定的)。
5．相干逻辑的命题逻辑系统是不可判定的(但仍是半可判定的)。
6．群论是不可判定的(但仍是半可判定的)。
7．集合论(如ZF系统、GB系统等)是不可判定的(但仍是半可判定的)。
8．一阶数论是不可判定的(但仍是半可判定的)。
9．“任一刁番图方程是否有整数解”(希尔伯特第十问题)是不可判定的(但仍是半可判定的，参见戴维斯－普特南－罗宾逊－马蒂亚谢维奇定理)。
10．群的字问题是不可判定的(参见群的字问题)。
(参见判定问题，可判定的问题)。