可判定语言

搜索到一个证据后回答“是”，通常比确认永远没有证据容易。可判定性要求把后者也完成：不属于语言时，机器必须在某个有限时刻明确回答“否”。

识别器不能错误地接受非成员，但可以不回答。这个不对称性正是可识别语言理路可识别语言Turing-recognizable language · Recursively enumerable language存在图灵机对语言内输入接受、对语言外输入可拒绝或不停机的语言。与可判定语言的区别：识别器的回答仍须正确，只是非成员一侧缺少终止保证。

一个完整的判定过程 ​

考虑 $L=\{a^n{b}^n:n\ge 0\}$。机器先检查输入是否由一段 $a$ 后接一段 $b$ 构成；出现别的符号或某个 $b$ 后再次出现 $a$，就拒绝。接着反复划掉最左边尚未匹配的 $a$，再划掉一个尚未匹配的 $b$。找不到对应 $b$ 时拒绝；所有 $a$ 都匹配后，检查是否还剩 $b$，有则拒绝，没有则接受。空串直接接受。

例如 aaabbb 经三轮匹配耗尽；aabbb 在匹配完两个 $a$ 后留下一个 $b$，因此拒绝。每轮至少减少一个未匹配的 $a$，且每次扫描的输入区间有限，所以算法必停机。说明“做什么”之外，还需要这个终止论证，才构成判定器。

有限图上的可达性同样可判定：逐个处理尚未访问的可达顶点，最多处理图中全部顶点。对上下文无关文法的成员问题，也可以用CYK 算法理路CYK 算法Cocke–Younger–Kasami algorithm用区间动态规划判定给定字是否属于 Chomsky 范式文法生成的语言。在有限表格中求出答案。

输入有限，不意味着运行有限 ​

程序源代码是有限字符串，却能描述无限循环。因此，给定程序和输入后问它是否停机，仍可能没有总能终止的判定器。停机问题理路停机问题不可判定性Halting problem · Undecidability of halting用总停机判断器的自反转构造证明 HALT 不可判定，并区分识别、有限步数检查与局部终止性证明。正是这样的例子：直接模拟能确认所有最终停机的实例，却无法把“一直没有停机”自动转化成有限时刻的否定结论。

可判定性暂时不限制时间效率。一个在所有输入上都停机、但可能运行指数甚至更久的算法仍是判定器。反过来，某个启发式程序在大量测试上快速结束，也不能替代对全部输入的正确性和终止证明。

正反两边都可识别，恰好就是可判定 ​

核心关系是

正向很直接：判定器本身识别 $L$；交换接受和拒绝状态，便得到补语言 $\bar{L}={\mathrm{\Sigma }}^{\ast }\setminus L$ 的判定器。因此 $L$ 也是余可识别语言理路余可识别语言Co-recognizable language · Co-r.e. language补语言可识别的单边可计算性；用交错模拟、停机反例与全称谓词区分负面证据和总停机判定。。

反向设 $A$ 识别 $L$，$B$ 识别 $\bar{L}$。在同一个输入上交替模拟 $A$ 一步、$B$ 一步。$A$ 接受就回答“是”，$B$ 接受就回答“否”。每个输入恰好属于两边之一，正确一侧的识别器必在有限步后接受；另一侧即使永远循环，也不会阻挡它。因此组合程序总能停机。

不能先把 $A$ 完整运行结束再启动 $B$，因为 $A$ 可能不结束；也不能仅交换一个识别器的接受、拒绝状态，指望得到补语言的识别器，因为原来的无限循环仍然存在。这两处都说明了“交替推进”的必要性。

可组合性与归约 ​

可判定语言对补、并、交封闭。对并集，先后运行两个判定器，再对结果取逻辑或；它们都必停机，所以组合程序也必停机。交集同理取逻辑与。

连接也保持可判定：长度为 $n$ 的字符串只有 $n+1$ 种切分 $w=uv$，逐一判断 $u\in L_1$ 和 $v\in L_2$ 即可。有限个切分配合总停机的成员测试，保证整个过程结束。

Kleene 星也保持可判定。对非空输入，只枚举把它切成非空连续片段的方案，共 $2^{n-1}$ 种，再逐段调用原语言判定器。允许空片段不影响结果，因为空片段可以删去，所以无需枚举无限多个空片段；空输入则因零次连接直接接受。有限性证明来自输入位置间只有有限个切点。

若存在总可计算的映射归约理路映射归约Mapping reduction · Many-one reduction用可计算函数把一个语言成员关系变换为另一个语言成员关系。 $f$，满足 $x\in A⟺f(x)\in B$，而 $B$ 可判定，那么先算 $f(x)$、再调用 $B$ 的判定器即可判定 $A$。取逆否命题：已知 $A$ 不可判定，且 $A$ 归约到 $B$，便推出 $B$ 不可判定。归约方向和 $f$ 的总可计算性共同保证这条推理。