§E15.13計算量階層定理

証明. 時間の場合を示す。(2)$\Rightarrow$(1)は直ちに分かる。実際、$T_{M'}(n)=\max_{|x|=n}\operatorname{time}_{M'}(x)\le c\,t(n)$がすべての$n$で成り立つので、$T_{M'}(n)=O(t(n))$である。

(1)$\Rightarrow$(2)を示す。(1)を仮定する。$M$を$L$の決定器とし、定数$C>0$と$n_0\in\mathbb N$が$T_M(n)\le C\,t(n)$（$n\ge n_0$）を満たすとする。$n_0=0$ならば$M'=M$と$c=C$をとればよいので、$n_0\ge 1$とする。

$\Sigma$は有限であるから、長さが$n_0$未満の語の全体

は有限集合であり、その要素数は$\sum_{j<n_0}|\Sigma|^{j}$である。したがって$L\cap F$も有限集合であり、この集合そのものを機械の有限制御へ組み込むことができる。具体的には次の$M'$をとる。$M'$の状態集合は、$M$の状態集合に、長さ$n_0$未満の各語$w\in F$に対応する状態$r_w$と、$n_0$個の記号を読み終えたことを表す状態$r^{\ast}$を加えたものである。$M'$は状態$r_{\varepsilon}$から始め、入力ヘッドを左端から右へ一マスずつ動かす。状態$r_w$で記号$a\in\Sigma$を読み、$|wa|<n_0$ならば状態$r_{wa}$へ移る。$|wa|=n_0$ならば状態$r^{\ast}$へ移る。状態$r_w$（$w\in F$）で入力の右端を検出したならば、その時点で入力は$w$に等しい。そこで、$w\in L$ならば受理状態へ、$w\notin L$ならば拒否状態へ移って停止する。この分岐は$L\cap F$という固定された有限集合に従って定めるものであり、有限個の状態の遷移先を固定することで実現することができる。状態$r^{\ast}$に達した場合には、入力ヘッドを左端へ戻したうえで$M$の初期状態へ移り、以後は$M$と同じ計算を行う。$M'$は作業テープへ何も書かないままこの前処理を行う。

$M'$が$L$を決定することを確かめる。$|x|<n_0$のときは、上の分岐により$x\in L$と$M'$が$x$を受理することは同値である。$|x|\ge n_0$のときは、$M'$は前処理の後に$M$と同じ計算を行うので、$M$の答えと一致する。$M$は$L$の決定器であるから、この場合も答えは正しい。いずれの場合も$M'$は停止するので、$M'$は$L$の決定器である。

時間を評価する。$|x|<n_0$のときは、前処理で入力ヘッドを右端まで動かして停止するので$\operatorname{time}_{M'}(x)\le n_0+1$である。$t(|x|)\ge 1$であるから$\operatorname{time}_{M'}(x)\le(n_0+1)\,t(|x|)$である。$|x|\ge n_0$のときは、前処理で$n_0$段の右移動と高々$n_0$段の左移動を行うので、

であり、再び$t(|x|)\ge 1$から$\operatorname{time}_{M'}(x)\le(2n_0+1+C)\,t(|x|)$である。したがって$c=2n_0+1+C$と置けば、すべての$x$で$\operatorname{time}_{M'}(x)\le c\,t(|x|)$が成り立つ。

空間の場合も同じ$M'$をとる。前処理は作業テープのヘッドを動かさないので、$M'$が訪れる作業マスは、$|x|<n_0$のときは各作業テープの初期位置だけであり、その総数は作業テープの本数$k$に等しい。$s(|x|)\ge 1$から$\operatorname{space}_{M'}(x)\le k\,s(|x|)$である。$|x|\ge n_0$のときは$\operatorname{space}_{M'}(x)=\operatorname{space}_{M}(x)\le S_M(|x|)\le C\,s(|x|)$である。したがって$c=\max\{k,C\}$と置けばよい。▨

証明.(1)を示す。時間構成機械を実行して$t(n)$の二進表記を得て、最下位ビット側にヘッドを置く。別の出力テープのヘッドは、まだ何も書いていない位置$0$に置く。二進カウンタが正である間、出力テープへ$1$を一つ書いて右へ進み、二進カウンタから$1$を減らす。減算では、最下位側から連続する$0$を$1$に変え、最初の$1$を$0$に変えた後、最下位位置へ戻る。

$t(n)$回の減算において、最下位ビットは高々$t(n)$回、その一つ上のビットは高々$\lceil t(n)/2\rceil$回、一般に第$j$ビットは高々$\lceil t(n)/2^j\rceil$回反転する。使用するビット数は$O(\log(t(n)+1))$なので、全反転回数と最下位位置へ戻る移動回数の和は

である。出力も一記号につき定数時間であり、もとの二進表記の生成時間も$O(t(n))$なので、全体は$O(t(n))$時間で停止する。

(2)を示す。空間構成機械を万能模倣し、各作業テープの各マスへ初めて入ったときだけ印を付け、二進カウンタを一つ増やす。もとの機械が停止した時点でカウンタは$s(n)$の二進表記を保持する。模倣領域はちょうど$s(n)$個のマスと固定個数の区切りを使用し、カウンタは$O(\log(s(n)+1))=O(s(n))$マスを使用する。次に、(1)と同じ二進減算を用い、カウンタが正である間、境界テープ上で現在位置を印付けて右へ一マス進む。時間には制限を課さないが、境界テープで訪れる位置はちょうど$s(n)$個である。模倣領域、カウンタ、および境界領域を合わせた使用空間は$O(s(n))$である。▨

証明.$M'$の状態集合、作業テープの本数、作業テープアルファベット、初期状態、および停止状態を$M$と同一にする。遷移関数を次のように定める。状態$q$、入力記号$a\in\Sigma$、および作業テープの走査記号の組$\vec b$に対する$M'$の遷移を、$M$の状態$q$、入力記号$1$、作業テープの走査記号$\vec b$に対する遷移と等しく定める。入力テープで空白（すなわち入力の右端の外側）を読んだ場合の遷移は、$M$の同じ状況における遷移と等しく定める。作業テープ側の書込みとヘッド移動、および入力ヘッドの移動は、いずれも$M$のものをそのまま用いる。

入力$x\in\Sigma^*$と$1^{|x|}$は同じ長さであるから、各時刻で入力ヘッドが同じ位置にある限り、$M'$が$x$上で読む記号が$\Sigma$の記号であることと、$M$が$1^{|x|}$上で読む記号が$1$であることは同値であり、$M'$が空白を読むことと$M$が空白を読むことも同値である。したがって遷移の段数に関する帰納法により、両者の状態、入力ヘッド位置、作業テープの内容、および作業ヘッド位置は各時刻で一致する。基底は初期配置の一致であり、帰納段階は上で定めた遷移の一致による。時間と空間の等式はこの一致から従う。▨

証明.$U$は第1テープへ機械符号$\langle M\rangle$、第2テープへ入力$x$を保存し、第3テープへ模倣配置を置く。第3テープでは、$M$の各作業テープの有限な使用部分を

と連結し、各$u_i$の走査位置に印を付ける。読取り専用入力テープをもつモデルでは、入力ヘッド位置を二進表記で同じ配置に加える。$M$のテープ本数$k$、状態集合、およびテープアルファベットは$\langle M\rangle$から有限時間で読み取る。

一つの模倣段では、最初に配置テープを左から右へ走査し、現在状態、入力ヘッド位置、および各作業テープの印付き記号を作業領域へ複写する。次に$\langle M\rangle$の遷移表を先頭から走査し、左辺が現在状態と走査記号列に一致する規則を探す。正しい決定性機械符号では規則がちょうど一つ存在する。最後に配置テープを再び走査し、書込み記号、ヘッドの印、および現在状態を更新する。ヘッドが$u_i$の右端から右へ進む場合には、区切り以後の有限文字列を一マスずつ右へ移して空白記号を挿入する。

$j$段の模倣後、各仮想ヘッドは初期位置から高々$j$マスしか移動していない。したがって、配置符号の長さは

以下であるような、$M$だけに依存する定数$d_M$が存在する。遷移表の走査時間は$O(|\langle M\rangle|)$であり、配置の二回の走査と、必要な場合の一回の挿入は$O(|x|+|\langle M\rangle|+j+1)$時間で終わる。よって、$j$段目の模倣時間は

以下であるような定数$e_M$が存在する。

$r\ge |x|$を用いて$j=0,\ldots,r-1$の時間を足すと、

を得る。機械符号と初期配置の構文解析および複写に要する$O(|\langle M\rangle|+|x|)$時間を定数へ吸収すれば、表示された上界になる。

模倣段数に関する帰納法により、第3テープを復号した配置は$M(x)$の同じ段数後の配置に等しい。基底は初期化から従い、帰納段階は遷移表から選んだ唯一の規則による更新から従う。したがって、$M$が受理または拒否へ到達した場合には、$U$は同じ模倣段で$M$の受理または拒否を検出する。▨

証明.$V$の有限制御を、$U$の有限制御と「時計内」または「時計切れ」という状態の直積にする。時計内の状態では、$V$の一遷移は$U$と同じ書込みおよびヘッド移動を模倣用テープ上で行うと同時に、専用の時計テープのヘッドを一マス右へ動かす。多テープ TM の一遷移は各テープのヘッドを同時に動かすので、時計を進めるための追加の遷移は必要ない。時計ヘッドが最初の空白へ到達した場合には、$V$は次の模倣遷移を行わずに時計切れとして停止する。$U$が受理状態または拒否状態へ移る遷移では、$V$も同じ遷移で対応する停止状態へ移る。

したがって、$V$が時計内で行う遷移と$U$の遷移は一対一に対応する。補題 2.1の定数を必要なら大きく取り直すと、$U$の初期化、機械符号の構文解析、配置の更新、および停止状態の検出を含む遷移数は$\widehat c_M(r+1)^2$以下である。表示された不等式の下では、この遷移数は時計長$B$より小さい。よって、$V$は時計切れより先に$M(x)$の結論を検出する。▨

証明. 仮定から$r(n)=O(T(n))$なので、$r$時間の決定器は同じ機械のまま$O(T(n))$時間の決定器でもある。したがって$\mathsf{DTIME}(r)\subseteq\mathsf{DTIME}(T)$である。

真の包含を示すため、言語$L_D$の決定器$D$を構成する。入力$x$の長さを$n$とする。$D$は最初に$x$が$\langle M\rangle\#1^k$という正しい形かを検査し、正しくなければ拒否する。正しい場合には、長さ$n$の一進列を作り、補題 1.2により時計テープへ$1^{T(n)}$を作る。$D$は時計ヘッドを列の先頭へ戻した後、補題 2.2の$V(\langle M\rangle,x)$を時計長$B=T(n)$で実行する。$V$が受理を報告したら$D$は拒否し、$V$が拒否を報告したら$D$は受理する。$V$が時計切れを報告した場合には、$D$は拒否する。したがって、時計の一記号が表すのは$M$の一段ではなく、万能模倣の初期化と配置更新を含む$V$自身の一遷移である。

ここで、$D$の時間を全段階について評価する。構文検査と長さ$n$の一進列の作成は$O(n)$時間である。時間構成機械の実行と$1^{T(n)}$の出力には$O(T(n))$時間がかかり、時計ヘッドを先頭へ戻す操作には高々$T(n)+O(1)$遷移が必要である。時計付き万能模倣は、時計切れまでに高々$T(n)+O(1)$遷移を実行する。停止結果の反転には定数時間しかかからない。$T(n)\ge n$なので、各段階の時間の和は

である。また、構文拒否、$V$の停止、または時計切れのいずれかが必ず起こるので$D$は決定器である。ゆえに$L_D\in\mathsf{DTIME}(T)$である。

$L_D\in\mathsf{DTIME}(r)$と仮定する。$r$は時間構成可能であるから§E15.10 定義 2.1により全ての$n$で$r(n)\ge1$であり、補題 1.1を適用することができる。したがって、ある決定器$M_i$と正の整数定数$a_i$が存在し、全ての入力$y$で

となる。$x_k=\langle M_i\rangle\#1^k$と置く。$k$を増やすと$n_k=|x_k|$は無限に増加する。時計付き万能模倣の補題で$M_i$に対応する定数を$c_i=\widehat c_{M_i}$とする。$r(n_k)\ge n_k$および$a_i\ge1$なので、同補題を被模倣段数$a_i r(n_k)$に適用することができる。little-o の仮定により、十分大きい$k$で

となる。最後の不等式では、固定された機械$M_i$に依存する定数$a_i$と$c_i$を$r(n)^2=o(T(n))$が吸収する。

unary padding$1^k$は、機械符号$\langle M_i\rangle$を変えずに入力長$n_k$を無限に増加させる。したがって、十分大きい$k$では、時計付き万能模倣は$T(n_k)$回の自分自身の遷移を使い切る前に$M_i(x_k)$の停止を検出し、$D(x_k)$は$M_i(x_k)$の答えを反転する。$M_i(x_k)$が受理すれば$x_k\notin L_D$であり、$M_i(x_k)$が拒否すれば$x_k\in L_D$である。$D(x_k)$と$M_i(x_k)$の答えが反対になることは、$M_i$が$L_D$を決定するという仮定に反する。ゆえに$L_D\notin\mathsf{DTIME}(r)$であり、包含は真である。▨

証明.§E15.10 補題 3.2を、作業テープの本数$k=1$、状態集合を$M$の状態集合、作業テープアルファベットを$M$の作業テープアルファベットとして適用する。§E15.10 補題 3.2 (1)が配置数の上界を与え、§E15.10 補題 3.2 (2)が停止しないことの結論を与える。同補題の定数を$c_M$とすればよい。同補題はこの定数を正の整数として与えるので、$b$が非負整数であることとあわせて、$c_M(b+1)$は正の整数である。▨

証明. 二段階で構成する。第一段階では§E15.10 定理 4.1を適用し、$M$が$x$上で停止するときに同じ受理または拒否を返し、一本の作業テープを用い、作業空間が$O(\sigma+1)$である決定性 Turing 機械$M_1$を得る。$M_1$の作業テープアルファベットを$\Gamma_1$、その大きさを$g$とする。

第二段階でアルファベットを三文字へ落とす。$\ell=\lceil\log_2\max\{2,g\}\rceil$と置き、$\Gamma_1$の各記号へ長さ$\ell$の相異なるビット列を割り当てる単射$\operatorname{code}\colon\Gamma_1\to\{0,1\}^{\ell}$を固定する。$M'$の作業テープを位置$0$から$\ell$マスずつの区画に分け、第$j$区画を位置$j\ell,\ldots,j\ell+\ell-1$とする。$M_1$の作業テープの位置$j$の記号が$a$であることを、$M'$の第$j$区画の内容が$\operatorname{code}(a)$であることによって表す。$M'$は各模倣段の開始時に、$M_1$の状態を自分の状態の一部として保持し、$M_1$の作業ヘッドがある区画の左端に自分の作業ヘッドを置く。

$M_1$の一段を次のように模倣する。$M'$は現在の区画を左から右へ$\ell$マス読む。最初のマスが空白記号$\square$であるならば、その区画はまだ一度も書かれていないので、$M_1$の空白記号の符号を$\ell$マスへ書き込み、区画の左端へ戻ってから読み直す。$\ell$は固定した定数であるから、読み取った$\ell$ビットを有限制御に保持し、$\operatorname{code}$の逆によって記号$a$を復元することができる。次に、$M_1$の遷移関数が状態と$a$と入力記号に対して定める書込み記号の符号を、同じ区画へ左から書き込む。入力ヘッドの移動は$M_1$と同一にする。$M_1$の作業ヘッドが右へ動くならば$M'$の作業ヘッドを$\ell$マス右へ、左へ動くならば$\ell$マス左へ動かし、次の区画の左端に置く。$M_1$の作業ヘッドが位置$0$で左移動を命じられた場合には、$M_1$の規約に従って同じ位置にとどまる。$M_1$が停止状態へ移る段では、$M'$も対応する受理状態または拒否状態へ移る。

模倣段数に関する帰納法により、各模倣段の開始時点で、$M'$の区画の内容は$M_1$の作業テープの内容の符号であり、保持している状態と入力ヘッド位置は$M_1$のものに等しい。基底は初期配置であり、帰納段階は上の手順による。したがって$M'$は$M_1$と同じ受理または拒否を返し、$M$が$x$上で停止する場合には$M'$も停止する。

空間を評価する。$M_1$が訪れる作業マスが$\sigma_1$個であるとき、$M'$が訪れる作業マスは$\ell\sigma_1$個である。$\sigma_1=O(\sigma+1)$であり、$\ell$は$M$だけから定まる定数であるから、$M'$の作業空間を$\gamma_M(\sigma+1)$以下にする定数$\gamma_M$が存在する。▨

証明.$s(n)=O(S(n))$なので、$s$空間の決定器は$O(S(n))$空間の決定器でもある。したがって$\mathsf{DSPACE}(s)\subseteq\mathsf{DSPACE}(S)$である。

三文字の作業アルファベットをもつ一作業テープ決定性 TM を、その有限な記述の符号によって列挙する。補題 4.2により、有限本の作業テープと任意の有限作業アルファベットをもつ決定器は、同じ言語を決定する三文字一作業テープ決定器へ、作業空間を定数倍しか増やさずに変換することができる。したがって、この列挙は空間計算量クラスの全ての決定器を定数倍の差まで含む。

言語$L_E$の決定器$E$を構成する。入力$x$の長さを$n$とする。$E$は補題 1.2と補題 1.3により$S(n)$マスの連続した境界を作る。後者により、入力$x$をそのまま読取り専用入力テープに置いたまま境界を作ることができ、$1^n$を作業テープへ書き写す必要はない。$x$が$\langle M\rangle\#1^k$という正しい形でない場合、または$|\langle M\rangle|>S(n)$の場合には拒否する。残りの場合には、$M(x)$を万能模倣し、模倣された$M$が$S(n)$個を超える作業マスを走査しようとしたら拒否する。

機械記述長と模倣空間がともに$S(n)$以下であり、$S(n)\ge\log_2(n+1)$である。したがって、状態番号、二つのヘッド位置、および三文字の作業テープを含む模倣配置は$O(S(n))$ビットで保存することができる。さらに補題 4.1の計数と同じ評価によって、可能な模倣配置数を数える。符号$\langle M\rangle$は$M$の遷移表を明示的に列挙する形で与えるので、$M$の状態集合$Q_M$について$\log_2|Q_M|\le|Q_M|\le|\langle M\rangle|\le S(n)$であり、作業アルファベットは三文字に固定されている。したがって、計数における状態数と作業アルファベットの寄与はいずれも$S(n)$の定数倍へ収まり、可能な模倣配置数が$2^{c(S(n)+1)}$以下であるような、模倣器だけに依存する正の整数$c$をとることができる。$S(n)$は非負整数であるから$c(S(n)+1)$は正の整数であり、$E$は$c(S(n)+1)$ビットの二進カウンタを用い、最大$2^{c(S(n)+1)}$段を模倣する。$M$がカウンタの終了前に受理すれば$E$は拒否し、拒否すれば$E$は受理する。カウンタが一周するまで停止しなければ、配置が反復しているので$E$は拒否する。

空間構成機械、万能模倣の記録、およびカウンタは、それぞれ$O(S(n))$マスを使用する。有限個の作業領域を一つのテープの別区間または定数個のトラックへ配置しても総空間は$O(S(n))$である。全ての分岐は有限時間で構文拒否、空間超過、模倣機械の停止、またはカウンタ終了へ到達するので、$E$は決定器である。ゆえに$L_E\in\mathsf{DSPACE}(S)$である。

$L_E\in\mathsf{DSPACE}(s)$と仮定する。$s(n)\ge1$であるから補題 1.1を適用することができ、さらに補題 4.2によって三文字一作業テープの形へ移すことができる。したがって、列挙中の一作業テープ決定器$M_i$と定数$a_i>0$を、$M_i$が$L_E$を決定し、全入力$y$で高々$a_i s(|y|)$マスを使うように選ぶことができる。$x_k=\langle M_i\rangle\#1^k$、$n_k=|x_k|$と置く。$s(n)=o(S(n))$であり$|\langle M_i\rangle|$は定数なので、十分大きい$k$について

が成り立つ。したがって、$E(x_k)$の万能模倣は空間超過で打ち切られない。

$M_i$は決定器なので$M_i(x_k)$は停止する。停止前に同じ配置を二度通れば決定性により停止しなくなるため、停止までの段数は許容空間内の配置数以下である。したがって、$E$はカウンタ終了前に$M_i(x_k)$の停止結果を得て、受理と拒否を反転する。$M_i(x_k)$が受理すれば$x_k\notin L_E$であり、$M_i(x_k)$が拒否すれば$x_k\in L_E$である。$E(x_k)$と$M_i(x_k)$の答えが反対になることは、$M_i$が$L_E$を決定するという仮定に反する。ゆえに$L_E\notin\mathsf{DSPACE}(s)$であり、包含は真である。▨

証明.$L\in\mathsf{NSPACE}(s)$とし、$L$を受理する非決定性 Turing 機械$N$と、すべての$x$について$\operatorname{space}_N(x)\le c_0\,s(|x|)$を満たす定数$c_0>0$をとる。定数を大きくしてもこの条件は保たれるので、$c_0$以上の正の整数を$a$とすれば、すべての$x$について$\operatorname{space}_N(x)\le a\,s(|x|)$である。以下、入力$x$を固定し、$n=|x|$、$b=a\,s(n)$と置く。$N$の状態集合を$Q$、作業テープの本数を$k$、作業テープアルファベットを$\Gamma$とする。

配置の集合と符号。$N(x)$の計算木に現れる配置では、各作業テープの訪問済み領域が$b$マス以下である。そこで、入力テープに$x$が置かれ、かつ各作業テープの訪問済み領域が$b$マス以下であるような配置の全体を$\mathcal C$とする。$a$と$s(n)$はともに正の整数であるから$b$は正の整数であり、$a\ge 1$から$b\ge s(n)\ge\lceil\log_2(n+1)\rceil$である。よって§E15.10 補題 3.2 (1)を適用することができ、$N$だけに依存する正の整数$c$によって$|\mathcal C|\le 2^{c(b+1)}$である。この主張は配置の個数だけを数えており、遷移関数が決定性であることを用いていない。各配置を、状態番号、入力ヘッド位置の二進表記、各作業テープの位置$0$から$b-1$までの内容、および各作業ヘッド位置の二進表記の組として符号化する。入力ヘッド位置は$\lceil\log_2(n+1)\rceil\le b$ビット、各作業ヘッド位置は$\lceil\log_2(b+1)\rceil\le b+1$ビットで表すことができるので、符号長は$N$だけに依存する正の整数$\lambda$によって$\lambda(b+1)$以下である。逆に、長さ$\lambda(b+1)$以下の語がこの形の正しい符号であるかどうかは、$b$マスの境界領域と有限制御によって判定することができる。したがって$\mathcal C$の元は、符号の辞書式順に一つずつ生成することができ、その生成に必要な空間は$O(b+1)$マスである。

配置グラフ。$\mathcal C$を頂点集合とし、$C$から$C'$へ辺があることを「$C'$が$N$の一段の遷移によって$C$から得られ、かつ$C'\in\mathcal C$である」ことと定める有向グラフを$G_x$とする。$G_x$における長さ$j$の路とは、$C_0,\ldots,C_j$であって各$C_u$から$C_{u+1}$へ辺があるものをいう。$j=0$の路も許す。

再帰手続き。$m=c(b+1)$と置く。$c$は正の整数であり$b+1$も正の整数であるから、$m$は正の整数である。$C,C'\in\mathcal C$と$0\le i\le m$を満たす整数$i$に対し、手続き$\mathrm{TEST}(C,C',i)$を次のように定める。

手続きの正当性。$\mathrm{TEST}(C,C',i)$が真を返すことと、$G_x$において$C$から$C'$へ長さ$2^i$以下の路が存在することは同値である。$i$に関する帰納法で示す。$i=0$の場合は手続きの定義そのものである。$i>0$とする。$\mathrm{TEST}(C,C',i)$が真を返したならば、ある$C''\in\mathcal C$について両方の呼び出しが真を返しており、帰納法の仮定により$C$から$C''$へ長さ$2^{i-1}$以下の路と、$C''$から$C'$へ長さ$2^{i-1}$以下の路が存在する。これらをつなぐと長さ$2^i$以下の路を得る。逆に、$C$から$C'$へ長さ$j\le 2^i$の路$C_0,\ldots,C_j$が存在するとする。$u=\lceil j/2\rceil$と置き$C''=C_u$とする。路の頂点はすべて$\mathcal C$に属するので$C''\in\mathcal C$である。$u\le\lceil 2^i/2\rceil=2^{i-1}$であり$j-u=\lfloor j/2\rfloor\le 2^{i-1}$であるから、帰納法の仮定により$\mathrm{TEST}(C,C'',i-1)$と$\mathrm{TEST}(C'',C',i-1)$はともに真を返す。手続きは$\mathcal C$のすべての元を試すので、遅くとも$C''$に到達した時点で真を返す。