可判定性与有效迭代 (Decidability and effective enumerability)
引入
我们已经碰到了很多类似的问题：给定一个集合 \(X\) 和性质 \(\mathcal{P}\) ，证明 \(X\) 中所有的元素都具有性质 \(\mathcal{P}\) . 但是很多时候，我们无法说明 \(X\) 和性质 \(\mathcal{P}\) 的关系，例如有些时候 \(X\) 中的元素有的并不具备性质 \(\mathcal{P}\) .
举个例子，所有的自然数对都有一个最大公约数，但是它们并不都是互素的.
在这样的情况下，我们需要更多描述
这样的集合的方法. 其中 \(\mathcal{P}(x)\) 表示 \(x\) 具有性质 \(\mathcal{P}\) . 此时我们更需要的其实是算法 (algorithm) ，因为它能帮助我们判定所有的对象是否具有性质，这远比只知道单个例子的结果更为重要.
还是刚才的例子，我们知道有 Euclid 算法（辗转相除法），此时我们就有了一个通用的处理最大公因数的方式.
此外，我们还想知道：一个问题是否有算法方法 (algorithmic solutions)，能否证明某个问题不存在一个可计算的算法？这些问题都引导我们研究可计算性理论.
可判定性 (Decidability)
可判定性的定义
定义：可判定性
一个定义在有限元素集合 \(X\) 上的性质 \(\mathcal{P}\) 被称为在 \(X\) 中可判定的，如果存在一个判定过程 (decision procedure) ，能判断给定的 \(x\in X\) 是否具有性质 \(\mathcal{P}\).
一个 \(X\) 的子集 \(A\) 被称为可判定的子集，如果通过 $$ (\mathcal{P}(x): \iff x\in A) $$
定义的性质 \(\mathcal{P}\) 是可判定的. （也就是是否属于 \(A\) 就定义为性质 \(\mathcal{P}\)） 对于上述的两种情况，若不是可判定的，则称为不可判定的.
一个函数 \(F: X\to Z\) 被称为可有效计算的 (effectively calculable)，如果存在一个有效过程 (effective procedure)，给定 \(x\in X\) ，都能计算出 \(F(x)\). 对任意 \(A\subseteq X\) ，其特征函数 (characteristic function) \(\mathrm{K}_A: X\to \left\lbrace 0,1 \right\rbrace\) 被定义为
$$ \mathrm{K}_A(x) := \begin{cases} 0, & x\notin A \ 1, & x\in A\end{cases} $$
这里面的定义都相对比较好理解，特征函数和实变函数中定义的也是基本一致的.
甚至用大白话也能讲清：一个集合是不是可判定的就看你知不知道里面有哪些元素.
从定义可以得到如下的两个性质：
性质
对任意的集合 \(A \subseteq X\) ，
- \(A\) 在 \(X\) 中可判定当且仅当其特征函数 \(\mathrm{K}_A\) 是可有效计算的.
- 如果 \(A\) 是有限的，那么 \(A\) 在 \(X\) 中是可判定的.
可判定性在已学集合中的体现
以下了解即可，证明可选择性地看，多数都和真值表有关.
定理：\(L\) 语句
集合 \(\mathrm{Sent}_L\) 在 \(\mathrm{Expr}_L\) 中可判定.
定理：真值指派
存在一个有效过程，使得给定 \(L\) 语句 \(\varphi\) 以及一个真值指派 \(V\) ，可计算出 \(V(\varphi)\) .
定理：重言式
重言式集合在 \(L\) 语句集合中可判定.
定理：命题理论
所有可有限公理化的命题理论都是可判定的.