巨大数研究 Wiki
Advertisement
巨大数研究 Wiki

\( \newcommand{\len}{ {\rm len}} \renewcommand{\value}{ {\rm value}} \newcommand{\ifu}{ {\rm if}} \newcommand{\gtone}{ {\rm gt1}} \newcommand{\parent}{ {\rm parent}} \newcommand{\diff}{ {\rm diff}} \newcommand{\ancestor}{ {\rm ancestor}} \newcommand{\bm}[1]{ {\boldsymbol  #1}} \newcommand{\w}{\omega} \newcommand{\e}{\varepsilon} \newcommand{\nat}{\mathbb{N}} \newcommand{\p}{\psi} \)

Y数列の展開ルールの説明

Y数列は足し算と引き算と大きさの比較くらいしか使わないので簡単です。小学生にも分かるように説明しようと思います。

Y数列の形

Y数列は \((a_0,a_1,a_2,\cdots,a_k)\) のように、有限個の要素から成り立つ有限数列の形をしています。例えば、(1), (1,1,1), (1,2,2), (1,2,3), (1,2,4), (1,2,3,4,1,2,3,3,3), (1,2,4), (1,2,4,5,4), (1,2,4,8,9,8), (1,2,4,8,16), (1,3), (1,4,4), (1,1024), という感じです。

Y数列の展開(\(\w\)まで)

Y数列は、ブラケット [] という1つのY数列と1つの整数 n を入力とし、1つのY数列を出力とする関数を使って「展開」をすることができます。あとで方法を書きますが、(1,2,3)[2]=(1,2,2,2)、という感じです。ここから、全てのY数列の展開方法を説明します。

まず一番簡単なのは、右端が 1 であるY数列の展開方法です。右端が 1 であるY数列を展開すると、その右端の1が消えるだけです。(1,1,1,1)[2]=(1,1,1)、(1,1,1,1,1,1)[100]=(1,1,1,1,1)、(1)[300]=() です。この場合にはブラケットの値には依存しません。これでひとまず \(\w\) までのY数列の展開ができます。

次に \(\w\) 以上のY数列の展開を説明します。

親を探す

(1,2,3,4,1,2,3,3,3)[2] を展開してみる

まず、( ) の中の全部の数字について、「親」というもの探します。その数字の左から順番に左に見ていって、初めて自分より小さな数が出てきたらそれが親です。例えば、下図の赤丸で囲まれた 3 の親を探します。

Koteitan explainy 00.png

となって、2 が親として見つかります。

1 には親がいません。


ヒドラ図を書く

すべての数字に対してそれぞれの親がどれかを調べて、それを下記のように線でつないで表します。これを Y 数列のヒドラ図と呼ぶことにしましょう。

Koteitan explainy 01.png

親の反対を子と呼びましょう。子を親の一段上に書くと書きやすいです。

1 には親がいないので、とりあえず左端の × につないでおきます。


Y数列の展開(\(\varepsilon_0\)まで)

親子の差が 1 である数列は下記の方法で展開することができます。

(1) まずブラケットを1つ増やします。
(2) 一番右の数字を消します。
(3) 消された数字の親に怒りのマークを付けます。(子が殺されたので怒るのです)
Koteitan explainy 02.png
(4) 怒った親を含む右部分は、「悪い部分(bad part)」と呼びます。親より左の部分は「良い部分(good part)」と呼びます。
Koteitan explainy 03.png
(5) 悪い部分をブラケットの数だけ右にコピーします。
Koteitan explainy 04.png

また、一番右の数字が 1 のときは、(1) でブラケットが 1 つ増えた後、1 の親がいないため、その 1 が単に消えて終わります。

ここまでの展開方法は、原始数列システムとほぼ同じです。親との差が 2 以上になるときは、また別のルールがあり、それを次で説明します。

Y数列の展開(\(\varepsilon_0\)~\(\varepsilon_{\omega+1}\))

下記で親子の差が 2 以上である数列の展開方法を説明します。例として (1,2,4)[2]を展開してみましょう。

(1,2,4)[2] の展開

Koteitan explainy 05.png
この数列では、親が 2、子が 4\ で、(4-2=2\) なので、親子の差が 2 の数列になります。この場合は、上記のように、(1,2,4) の親子の差を書いた数列である (1,2) という2つめの数列を作って、同じように枝を書いてやります。親と子の差を取るため、毎回隣との差を取る一般的な数列でいうところの階差数列とは違うのですが、この親と子の差を取った数列をY数列での階差Y数列と呼びましょう。階差Y数列 (1,2) を (1,2,4) の対応する枝にの下に書いてやるのが分かりやすいです。この (1,2,4) を「1段目のY数列」、その階差Y数列 (1,2) を「2段目のY数列」と呼ぶことにします。
展開するには、まずは、この2段目の数列をいままでと同じルールで展開します。
Koteitan explainy 06.png
(1,2) → (1,1,1) となりますね。太字の 1 が bad root です。

そしてそれを使って次は1段目のY数列を再構成してやることになります。その前に、1段目のY数列も2段目のY数列と同じように bad part をコピーする必要があります。

まず、1段目のY数列の bad root がどこになるかと言うと、2つ目のY数列の bad root に対応する枝の先、つまり、この場合は 2 が1段目のY数列の bad root になります。bad root とそれから右が bad part です。この場合は 2 で終わりなので、bad part は 2 だけです。

コピーするときは2段目より少し特殊な方法が必要です。まず、最初のY数列 (1,2,4) の bad part の「枝の繋がり方」を分析する必要があります。
Koteitan explainy 07.png
bad root の親の場所(IN)と刈られた子のあった場所(OUT)の高さに注目します。IN は bad root より一段下に、OUT は bad root よりも1段上の段にありますね。そして、コピーする際にはこの情報を使って、コピーされた bad part の IN が、ひとつ左の bad part の OUT につながるようにコピーするのです。 Koteitan explainy 08.png
このようになります。コピーされた bad part は数字を書かずに、数字は〇にしておきます。形が決まったら、2段目のY数列が1段目のY数列の階差Y数列なるように1段目のY数列を再構築します。
Koteitan explainy 09.png
再構築は全て加算で行うことができましたね。1+1=2, 2+1=3, 3+1=4, という感じです。そして、この1段目のY数列が、元のY数列を展開した数列となります。(1,2,4)[2] を展開して出来る数列は、(1,2,3,4) ということです。

(1,2,4,1,2,4)[2] の展開

今度は (1,2,4,1,2,4)[2] を展開してみましょう。
420px
ひとつだけ先ほどと違うことがあります。 (1,2,4,1,2,4) の右の1 は親が無いので、階差Y数列が作れません。この場合は親を×と表記しておきましょう。

あとは同じで、階差数列 (1,2,x,1,2) を [2] で展開して (1,2,x,1,1,1)として、それをもとに1段目のY数列を展開します。(1,2,4,1,2,3,4) となります。

ちなみにこれは \(\e_02\) に対応するY数列になります。

(1,2,4,4)[2] の展開

次は(1,2,4,4)[2]の展開をやってみます。これはさっきと同じルールで展開できます。
Koteitan explainy 11.png
まず、2段目の bad root は、最右 2 の親なので 1 になります。bad part はその右なので、(1,2)になります。これを右にブラケット回コピーします。(1,2,1,2,1,2)になりました。では1段目はどうコピーされるかを考えます。
Koteitan explainy 12.png
IN は bad root の一つ下、刈り子は 4 で、親は 2 なので、OUT は bad root の一つ上です。これを IN と OUT を繋いで、枝のコピーをします。
Koteitan explainy 13.png
そして、先ほどと同じように、2段目の数字をヒントに、1段目のY数列を再構成していきます。枝に対応するところを足し算していきます。2+1=3, 3+2=5, 3+1=4, 4+2=6 という風に、〇が 3,5,4,6 で埋まります。(1,2,4,4)[2]=(1,2,4,3,5,4,6) ということですね。

このルールで \(\epsilon_{\w+1}\) 未満までを展開することができます。

Y数列の展開(\(\varepsilon_{\omega+1}\)~\(\p_0(\p_\w(0))\)

気を付けないといけないことが、(1,2,4,5,4) で生じます。これは \(\varepsilon_{\omega+1}\) に相当するY数列です。

先ほどと同じ考えでいくと、階差数列は(1,2,1,2)となるので、
Koteitan explainy 14.png
のように、右端の 2 の親をその左隣の 1 にしたくなります。しかし、2段目以降のY数列では、親の決定に上の行が絡んできます。
Koteitan explainy 15.png
まず、1段目の右端の 4 の直系先祖を観察します。直系先祖とは、自分、親、親の親、親の親の親、…を指します。4 の直系先祖は、4、4 の親の 2、その親の 1、その親の × となります。右から3つ目の 4 と 5 は直系先祖ではありません。

そして、2段目の要素の親を見つけるときには、その要素に対応する1段目の枝につながっている親子の直系先祖たちの枝に相当する2段目の要素しか候補になりません。つまり、2段目の右から3つ目の 2 や右から2つ目の 1 は無視されます。

これによって、2段目の右端の親は右から4番目の 1 になります。

あとは今までと同じです。
Koteitan explainy 16.png
2段目の bad root は一番左の 1、bad partは(1,2,1)です。 1段目の bad root は 2、bad partは(2,4,5)です。 これをブラケット分コピーして、2段目は(1,2,1,1,2,1,1,2,1)となり、 1段目は2段目の数字を使って〇を埋めて(1,2,4,5,3,5,6,4,6,7)となります。

これで(1,2,4,8)未満、つまり、2段目までの数列が存在するY数列を展開することができます。

Y数列の展開(\(\p_0(\p_\w(0))\)~\(\p_0(\p_\w(1)+\p_\w(0))\))

次は3段目が生じる数列の話です。(1,2,4,8,8)[2]を展開してみましょう。 Koteitan explainy 17.png
2段目のY数列(1,2,4,4)を展開したいのですが、ここで親子の差分が 2 な組が出てきます。この場合はさらにこれの階差Y数列、3段目のY数列を作ります。

この場合、1段目の数列は\(\e_0\)未満の数列と同じで単なるコピー、2段目Y数列と1段目Y数列は、先ほどのような、枝の形のコピー後に下の段のY数列から再構築することになります。

つまり、3段目Y数列 (1,2,2) がまず(1,2,1,2,1,2)と展開され、2段目Y数列は(1,2,4,3,5,6,4)と再構築され、さらにそれを使って1段目Y数列(1,2,4,8,7,12,11,17)が再構築できます。

Advertisement