可判定性

判定问题要求对规定范围内的输入回答是或否。例如给定一个非负整数，问它是否为偶数；给定有限自动机和字符串，问自动机是否接受该串。把肯定实例的编码收集起来，就得到与这个问题对应的形式语言。

若有算法对每个输入都停机，并且总能正确地区分肯定与否定实例，问题就是可判定的。只在部分测试上答对还不够；永不返回的程序也不能算已经给出否定答案。有限自动机的字符串接受问题可判定，因为逐符号模拟后就能检查最终状态。

参考：[1]

半判定性也称可识别性：存在算法，在所有肯定实例上最终接受，而在否定实例上可以拒绝，也可以一直运行。停机问题给出直观例子：输入一个程序及其输入，问这次运行是否终止。直接模拟会在原程序停机时确认“是”，但等了再久仍未停机，都不足以确认它永远不会结束。

若一个问题和它的否定问题都可识别，就能交替推进两个识别过程。每次各运行有限步，等待其中一个接受；因为每个输入恰好属于一边，最终一定得到答案。这说明可判定性不只是有一个寻找证据的过程，而是两种答案都具有终止保证。

参考：[2]

停机问题不可判定，排除的是对任意程序及任意输入都正确并停机的统一算法，并不是说每个具体程序都无法分析。例如一个直接返回的程序显然终止，一个没有退出条件的固定循环也可能很容易证明不终止；这些特例不构成通用判定方法。

证明不可判定可使用对角论证，或把已知不可判定问题归约到目标问题。后一方法必须给出有效转换：如果目标问题能被判定，借助转换就能判定原问题，于是与已知结论矛盾。仅仅没有找到算法，不足以完成这类证明。

参考：[2]

可判定性问“原则上是否有算法”，计算复杂性进一步问时间和空间要多少。一个肯定会结束的穷举过程可能完全不实用，但仍能证明可判定。例如有限列表中是否存在若干项相加等于指定值，可以逐个检查所有子集；列表增大时，检查量可能迅速增长。

“尚未解决”描述目前的知识状态，“不可判定”则需要在明确计算模型和输入范围下证明算法不存在。实际工具也可限制程序种类、设置资源上限，或在部分情形回答“不知道”；这些有用的做法并不等于解决了原来的通用判定问题。

参考：[3]