入力の検査の限界

入力（文字列）と呼び出し（$Q$ の元）をそれぞれ自然数で符号化し、モデルを「入力から呼び出しへの部分計算可能な写像」とみなす模型を考える。有害とみなす呼び出しの集合を $B$（$\varnothing \ne B \subsetneq Q$、所属は決定可能）とする。$\varphi_0, \varphi_1, \ldots$ を部分計算可能関数の受理可能な番号付けとし、その万能関数 $(e, y) \mapsto \varphi_e(y)$ は部分計算可能であるとする。

1. 番号 $e$ を入力として「$\varphi_e(0)$ が定義されて $B$ に属するか」を判定するアルゴリズムは存在しない。
2. モデル $U$ を $U(x) = \varphi_x(0)$ と定めると（万能関数により、$U$ は部分計算可能な写像である）、$U$ に有害な呼び出しをさせる入力の集合 $\mathrm{Harm}_U = \{x : U(x) \in B\}$ は決定不能である。
3. したがって、入力だけを見て「止める」「通す」を決めるどんな決定可能な検査 $K$（止める入力の集合）についても、$K \ne \mathrm{Harm}_U$ である。すなわち、$U$ に対しては、有害な入力を通す（見逃し）か、無害な入力を止める（誤検出）かの少なくとも一方が必ず起こる。