可判定、半可判定、不可判定

上级：logic

这套词汇回答的是一个问题:"一个算法能不能把这件事解决掉?"

三个层级

一个集合/谓词 S（比如自然数集，或字符串集）可以是:

• 可判定（递归的）——存在一个算法，对每一个输入都会停机，并回答"x ∈ S?"是或否；
• 半可判定（递归可枚举，r.e.）——存在一个算法，恰好在成员上停机并给出"是"，而在非成员上可能永远运行下去；
• 不可判定——即不是可判定的。

那座桥

S 可判定 ⟺ S 及其补集都半可判定。 (把两个半判定算法并行跑起来，必有一个会停机；反过来，一个判定算法自然对两边都能半判定。)

所以不可判定性是一种单边性：halting-problem 是半可判定的（等着看它停机就行），但不是余半可判定的（你没法确认它不停机）——因而不可判定。几乎所有"程序 P 是否具有某个语义性质 Q"这类问题，都会被Rice 定理判为不可判定；而新的不可判定问题，则不断地靠归约从停机问题这里铸造出来（generalized-collatz、FOL validity、Post 对应问题……）。

这正是 the r.e. tier 背后的那个性质，也是 you relax 才能换来可用答案的原因，更是"这个 agent/循环到底会不会终止？"这个问题的天花板（recursion-is-a-phase-transition）。