Fandom

巨大数研究 Wiki

コメント4

バシク行列 計算可能性の証明

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

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

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

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

\(B_n\leq_rB\)

が恒に成り立たなければならない。

\(\leq_r\) は推移律が成り立ち・・・

具体的にはバシク行列系の具体的な定義によるが、

\(B'_k=_rB_k\quad k<n\) かつ \(B'_n\leq_rB_n\) のとき、

\(B'_0\frown B'_1\frown\cdots\frown B'_n\leq_r B_0\frown B_1\frown\cdots\frown B_n\)

が成り立つ。

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

具体的な証明

定義はバシク氏のものによる。計算過程を悪い部分ごとに組織立て、全体の証明を次の二つに分解する。

  • その悪い部分の右端に来るコピーが、ある比較方法で恒に小さくなる(ある比較方法で整列可能である)。
  • 悪い部分の列の長さが無限に長くなることはない。

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


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

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

Fandomでも見てみる

おまかせWikia