Fandom

巨大数研究 Wiki

ベクレミシェフの虫

548このwikiの
ページ数
新しいページをつくる
コメント0 シェアする

ベクレミシェフの虫 (Beklemishev's worms) は、 Lev D. Beklemishev (ロシア語: Беклемишев Лев Дмитриевич[1][2][3])が記述した終了までに長い時間がかかる1人ゲームである[4]ヒドラゲームにたいへんよく似ている。また、原始数列システムはこれによく似ている。

説明 編集

虫は非負整数のリストである \([W_0, W_1, \ldots, W_n]\)。ベクレミシェフが「虫の闘い」と呼ぶゲームは、我々のヒーローであるセドリックが、任意の虫 \(W\) とともに登場し、その虫を空のリストにすることが彼の仕事である。ゲームの \(m\) 番目のステージでは、次の関数 \(\text{next}(W, m)\) によって虫が変化する。

  • \(W_n = 0\) であれば、 \(\text{next}(W, m) = [W_0, W_1, \ldots, W_{n-1}]\) となる。(すなわち、セドリックが虫の頭を切り落とす。)
  • そうでなければ、数列の良い部分 g と悪い部分 b を、次のように決める。\(i<n, W_i<W_n\) をみたすiが存在するかどうかを考える。
    • i が存在しないときは \(g=[ ], b=[W_0, \ldots, W_{n−1},W_n −1]\) とする。
    • i が存在するときは \(k = \max \{i; i<n, W_i<W_n \}\) とおき、\(g=[W_0,\ldots,W_k], b= [W_{k+1},\ldots,W_n -1]\) とする(\(W_n\) が 1 減っていることに注意)。

そして、 \(\text{next}(W, m) = g + b + b + \cdots + b + b\) (\(m+1\) 個の \(b\))とする。ここで、 + は数列の連結であり、たとえば [0, 3, 2] + [1, 4, 5] = [0, 3, 2, 1, 4, 5] である。

ベクレミシェフは、彼が虫の法則と名付けた定理を証明した。それは、セドリックは \(W\) の初期値に関わらず、常に虫に勝つことができる、というものである。さらに、この事実がペアノ算術では証明不可能であることを証明した。

このことから、増加速度が速い関数を作ることができる。\(\text{Worm}(n)\) を、 \(W = [n]\) から始めて虫に勝つために必要なステップ数とする。すると、 \(\text{Worm}(n)\) は、いかなるペアノ算術による証明可能帰納関数も支配する。この関数の増加速度は \(f_{\varepsilon_0}(n)\) 程度である。

編集

  • Start: [1]
  • Step 1: [0,0]
  • Step 2: [0]
  • Step 3: []

すなわち \(\text{Worm}(1) = 3\)

  • Start: [2]
  • Step 1: [1,1]
  • Step 2: [1,0,1,0,1,0]
  • Step 3: [1,0,1,0,1]
  • Step 4: [1,0,1,0,0,0,0,0,0]
  • Step 10: [1,0,1]
  • Step 11: [1,013]
  • Step 24: [1]
  • Step 25: [026]
  • Step 51: []

すなわち \(\text{Worm}(2) = 51\)

出典 編集

  1. [1]
  2. [2]
  3. [3]
  4. Beklemishev, L. D.The Worm principle”, Logic Colloquium '02 (Münster, 2002)

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


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

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

Fandomでも見てみる

おまかせWiki