递归可枚举集和关系 (Recursively enumerable sets and relations)
背景讨论
定义：可有效枚举的
一个有限集合 \(X\) 称为可有效枚举的(effectively enumerable) ，如果：
- \(X\) 是空集；
- 或者存在一个可有效计算的函数 \(F:\omega\to X\) ，其能枚举 \(X\) —— 意思是说，\(X=\mathrm{Im}(F):= \left\lbrace F(n) : n\in \omega \right\rbrace\).
定义：半可判定过程
对于任意的集合 \(A \subseteq X\) ，\(A\) 在 \(X\) 中被称为半可判定的 (semi-decision procedure) ，如果存在一个半可判定过程，可理解为：
存在一个程序来判定 \(x\in A\) ，如果 \(x\in A\) ，则其将在有限步后终止，并回答 "yes" ，否则将会永不终止.
这是一个很有趣的定义，按照这个理解，我们容易得到如下的性质.
半可判定性的性质
- 如果 \(A\) 在 \(X\) 中是可判定的，那么 \(A\) 在 \(X\) 中是半可判定的.
- 如果 \(A\) 是可有效枚举的，那么 \(A\) 在 \(X\) 中半可判定.
- 如果 \(A\) 和 \(X\sim A\) 在 \(X\) 中半可判定，那么 \(A\) 在 \(X\) 中可判定.
- 如果 \(X\) 是可有效枚举的，且 \(A\) 在 \(X\) 中半可判定，那么 \(A\) 是可有效枚举的.
(1) 根据定义结论是显然的.
(2) 这个相对比较好理解，如果 \(A\) 是可有效枚举的，那么此时若 \(x\in A\) ，就存在 \(F(n_x)=x\) ，经过 \(n_x\) 步可判定 \(x\in A\) .
反过来，若 \(x\not\in A\) ，那么 \(F\) 将会沿着 \(\omega\) 不断计算下去，永不终止，从而 \(A\) 是半可判定的.
(3) 这个我们不妨用比较容易理解的思路：让判定 \(A\) 和 \(X\sim A\) 的两个程序并行，那么经过有限步必定会有一方停止，此时已经可以判定 \(x\in A\) 和 \(x\in X\sim A\) 的正确性了.
(4)
递归枚举
递归可枚举
定义：递归可枚举
集合 \(X \subseteq \omega\) 称为递归可枚举集 (recursively enumerable or r.e.)，如果 \(X=\varnothing\) 或存在一元函数 \(F\)，\(X = \mathrm{Im}(F)\).
结合可有效枚举，递归可枚举实质上就是指存在函数 \(F\) 可枚举 \(X\) ，注意这个 \(F\) 并不需要是单射以及递增的.
命题
所有的递归集都是递归可枚举的.
命题
对于任意的 \(X \subseteq \omega\) ，\(X\) 是递归可枚举的当且仅当存在递归二元关系 \(R\) ，使得
$$ X = \left\lbrace m: \exists p R(m,p) \right\rbrace $$
半可递归
定义：半可递归
关系 \(P \subseteq \omega^k\) 是半可递归的，如果存在递归关系 \(R\) ，对于所有的 \(m_0,\cdots,m_{k-1}\) ，
$$ P(m_0,\cdots,m_{k-1})\iff \exists p R(m_0,\cdots,m_{k-1},p). $$
我们称 \(P\) 是 \(R\) 的一个投影(projection)，并且写为 \(\exists R\).
此外，\(P\) 称为 (co-semi-recursive) 的，如果其补集 \(\omega^k\sim P\) 是半可递归的.