マッチは決定可能だが、効果についての性質は決定不能である

文字の有限集合の上の文字列をコマンドとする。

1. * を任意の文字列に当てるワイルドカードのパターン $\pi$ とコマンド $c$ について、$c \models \pi$ かどうかは決定可能である。したがって、有限の規則集合 $R$ について $\mathrm{Mat}_\kappa(R)$ は決定可能な集合である。
2. パス $p$ を固定し、$W_p$ を「実行すると $p$ に書き込むコマンド」の集合とする。コマンドの言語が任意のプログラムを実行できる、すなわち、計算可能な写像 $e \mapsto c_e$ で「$c_e$ を実行すると $p$ に書き込む $\iff$ 番号 $e$ の部分計算可能関数 $\varphi_e$ が入力 $0$ で停止する」を満たすものがあるとする。このとき $W_p$ は決定不能である。
3. 2 の仮定のもとで、どんな有限の規則集合 $R$ についても $\mathrm{Mat}_{\mathrm{deny}}(R) \ne W_p$ である。すなわち、$p$ に書き込むのに deny にマッチしないコマンドがあるか、$p$ に書き込まないのに deny にマッチするコマンドがある。