Upper-Branch-Ignoring モデルを使ったバシク行列のヒドラ表現

６月くらいに考えた Upper-Branch-Ignoring モデル (上枝無視モデル) というバシク行列(BM4)のヒドラ表現を紹介します。(バシク行列の展開ルールと、この記事内の数式については、バシク行列の数式的定義 を見てください。バシクさんのオリジナルの定義はこちらにあります。)

先行研究

BM4 の bad root 探索の方法については、Bubby3 さん、Ecl1psed276 さん、Alemagno12 さんが下記の記事で分かりやすく説明してくれています。

• Bubby3, BM1 は期待より弱い -その修正方法
• Ecl1psed276 and Alemagno12, BM2 のプログラムフリーな定義？

これらの方法は内容は同じで、Ecl1psed276 さん、Alemagno12 さんはこの方法を sequence reduction method (数列削除法) と呼び、Bubby3 さんは upper-branch removing method (上枝削除法)と呼んでいます。

Bubby3 さんは下記のように (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1) という行列を例に upper-branch removing method を使った bad root の見つけ方を説明してくれています。

1. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
2. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
3. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
4. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
5. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
6. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
7. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)

この方法は、上記のように注目ノードよりも高さが低いノードを探しながら、スキップされたノードのある列を数列から消していく方法となっています。

この説明は非常にシンプルなのですが、探索の間中、削除操作によって行列がどんどん動的に変わっていくので、上昇行列 \(A_{xy}\) を求める時と次の展開をするときに行列をたくさん書かないといけなくなります。

提案

そこで、この数列削除法の動的な挙動を静的に表せる図の書き方を考えたのが Upper-Branch-Ignoring モデル です。

Fig.1 Upper-Branch-Ignoring モデル

Upper-Branch-Ignoring モデルの図は、行列の行数 \(Y\) と同じ数のヒドラから成っています。各ヒドラの各ノードの高さは行列 \(\mathrm{S}\) の要素の値 \(S_{xy}\) と一致します。各辺は親ノード \(P_y(x)\) への繋がりを表しています。その接続は最上行のヒドラは原始数列数のヒドラ表現そのものですが、２行目以降は異なってきます。

Fig.2 Mistake

２行目以降のヒドラの接続は、上の行の影響を受けるのです。

下記が下の行のヒドラの接続の書き方です。

Fig.3 ヒドラの書き方

Fig.3-1 の赤色('子'と呼びましょう)の親を探して線を接続することを考えます。

まず、子と同じ列にあるひとつ上の行のヒドラのノードを緑のようにマークします(Fig.3-1)。次にその直系先祖全て \(\forall a(P_{y-1})^a(x)\) をマークします(Fig.3-2)。最後にその上の直系先祖と同じ列にある当該行のヒドラのノードだけを見ながら(Fig.3-3)、子の高さよりも低い高さにある最右のノードを探して線を繋ぎます(Fig.3-4)。これが親 \(P_{y}(x)\)です。

この図は静的なので、bad root 探索と上昇行列の決定に便利です。下記はその方法です。

Fig.4 bad root探索、上昇行列、コピー

これは (0,0,0)(1,1,1)(2,0,0)(1,1,1) の例です。 (これは BM1 が停止しない有名な行列です) 行列の bad root \(r\) は最右の刈られる子 \(X-1\) の非零最下行 \(t\) の要素 (\(\mathrm{S}_{X-1}=\)(1,1,1)) の親 \(P_t(X-1)\) と定義されます。

上昇行列 \(A_{xy}\) は、それらの再帰的な子孫(\(\{\forall x|\forall ar=P^{a}_y(r+x)\}\)) です。以上です。非常に簡素に終わりました。ピンクのノード は bad root の子孫ではないので、上昇せず、元の高さをキープしたままコピーされます。

また、コピーのときも、この親の木構造をそのままコピーすればいいので楽です。次の展開の時に再度親の接続の解析をする必要はありません。

このように、Upper-Branch-Ignoring モデルを使うと bad root 探索、上昇ノードの決定、コピーが簡単かつ静的に分析＆実行できます。

続く?

この図を使って、また別の非常に面白いバシク行列の特性を見つけました。その話はまた別の記事で…

表記例

下記は Upper-Branch-Ignoring モデルを使った図の例です。

Fig.5-1 例:(BM1 が停止しない行列)

Fig.5-2 例:(BM2 が停止しない行列)

参考文献

• この Wiki での バシク行列システム の説明 (注:ルールは BM1 です。)
• Bubby3, 'BM1 is weaker than expected. #How to fix it', Googology wiki blog, Mar. 25, 2018.
• My first post about Upper-Branch-Ignoring Model, 2, 3, twitter, June 17, 2018
• Ecl1psed276 and Alemagno12, 'A program-free definition for BM2?', Googology wiki blog, July 9, 2018.
• Bashicu, ' BASIC言語による巨大数のまとめ', 巨大数研究 wiki blog, Sept. 1, 2018.
• Koteitan, 'Purely mathematical definition of Bashicu Matrix', Googology wiki blog, Sept. 24, 2018.