FANDOM


全体の証明、もしくは計算可能な定義の趣旨

行列 \(G\frown B\frown N\) をβ-簡約して

\(G\frown B_0\frown B_1\frown\cdots\frown B_n\)

が得られたとする。このとき、

\(B_k\frown N_k<_rB\frown N\)

が恒に成り立たなければならない、ただし \(N_k\) は \(B_{k+1}\) の最初の列。

述語 \(<_r\) は悪い部分ごとに定義される。

ヒドラツリーの性質より、以上で計算が終了するための十分条件となる。

具体的な証明

定義はバシク氏のものによる。\(G\frown B\) の計算が終了することが証明されたものとし、計算過程を悪い部分ごとに組織立て、帰納的に証明する。全体の証明を次の二つに分解する。

  • 計算過程において、その悪い部分の系列にあたる行列の集合がある比較方法で整列可能である。
  • 悪い部分の列の長さが無限に長くなることはない、つまりツリーの構造が(証明の基準としている悪い部分よりも下に)無限下降列をもつことはない。

悪い部分に足されたΔの値のみからなる行列をその悪い部分の基底とする。値が基底に達したところからその悪い部分はヒドラツリーの要領で展開される。

ヒドラの拡張として考えたほうが分かりやすいかもしれない。ユーザーブログ:KurohaKafka/バシク行列のブーフホルツのヒドラを応用した表現を参照。

標準形とされるすべてのツリーからなる集合が、計算順序において整列可能であることを示せばよい。

en

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

FANDOMでも見てみる

おまかせWiki