有限のテストの不完全性

仕様 $(D, S)$ を満たす実装 $f$ が存在するとし、$T \subseteq D$ をテスト集合、$O$ を正確なオラクルとする。

1. ある $x^{*} \in D \setminus T$ と $y^{*} \in Y$ について $(x^{*}, y^{*}) \notin S$ であるとする。このとき、$T$ に合格し、仕様 $(D, S)$ を満たさない実装 $g$ が存在する。$g$ は、$f$ に「入力が $x^{*}$ と等しいか」を調べる分岐を 1 つ足したものにとれる。
2. とくに $D$ が無限集合で、$S$ がどの入力についても何らかの出力を禁じている（すべての $x \in D$ に $(x, y) \notin S$ となる $y$ がある）ならば、どんなテスト集合 $T$ についても (1) の $g$ が存在する。
3. 逆に $D$ が有限で $T = D$ ならば、「$f$ が $T$ に合格する」ことと「$f$ が仕様を満たす」ことは同値である。