BB(3, 4) > Ack(14) の結果

 (sligocki.com)
1 ポイント 投稿者 GN⁺ 2024-05-25 | 1件のコメント | WhatsAppで共有

BB(3, 4) > Ack(14)

  • 2024年5月22日
    • Pavel が3状態4記号チューリングマシン（Turing Machine, TM）を発見
    • この機械は「Ackermann級」関数を計算し、正確に (2↑155)+14 個の非ゼロ記号で停止する
    • Knuth の上向き矢印記法はやや扱いづらいため、これを次のように近似できる: BB(3,4)>Ack(14)
    • ここで Ack(14) は14番目の Ackermann 数として定義される: Ack(n)=n↑nn
    • この機械は「自然発見された」ものとして初めて Ackermann級関数をシミュレートできる TM である

機械

  • 状態遷移表

    | 0   | 1   | 2   | 3   |
| --- | --- | --- | --- |
| A   | 1RB | 3LB | 1RZ | 2RA |
| B   | 2LC | 3RB | 1LC | 2RA |
| C   | 3RB | 1LB | 3LC | 2RC |

  • 最終構成

    • 0∞32g153(0)+12161 Z> 0∞
    • 正確に σ=2g153(0)+18=(2↑155)+14 個の非ゼロ記号がテープに残る

Attribution

  • 発見者
    • この TM は Pavel Kropitz(@uni) によって発見され、2024年4月25日に Discord で共有された
    • 彼のコードでは TM スコアに対する人間可読な境界を指定できず、単に Halt(SuperPowers(13)) と記されていた
    • 彼は新しい「帰納的証明検証器」を用いてこの結果の検証を開始した
    • 2024年5月20日に正確な gkn(m) の定義を抽出し、σ>2↑153 の境界を得た
    • Matthew House(@LegionMammal978) は 2024年5月22日に gkn(0)=2↑k(n+2)2−2 という単純な閉形式を発見した

解析

  • B(k,n,m) の定義

    B(k,n,m)=0∞32m+12k A> 1n

  • 証明

    0∞A>0∞→241B(16,3,0)20∞
B(k,n,m)→B(k,0,gk−1n(m)) if k≥1
B(k,0,m)2→10∞32m+12k1Z>

  • gk(m) の定義

    g0(m)=m+1
gk+1(m)=gk2m+2(0)

二重帰納法による証明

  • 主要な規則

    B(k,n,m)→B(k,0,gk−1n(m))

  • Lemma 1

    For all k≥1: 32k<B→2k+12k<B1

  • Corollary 2

    For all k≥1,m≥0: 3m2k<B→(2k+1)m2k<B1m

  • Theorem 3

    For all k≥1,n≥0,m≥0: B(k,n,m)→B(k,0,gk−1n(m))

正確な値

  • Theorem

    For all k≥0,m≥0: 2gk+1(m)+4=2↑k(2m+4)

  • Corollary

    For all k≥0,n≥0: 2gkn(0)+4=2↑k(n+2)

  • 結論

    σ=2g153(0)+18=(2↑155)+14

Permutations

  • 状態 B から開始

    σB=2g63(0)+9=(2↑65)+5

  • 状態 C から開始

    σC=2g03(0)+3=(2↑05)−1=9 (72ステップで停止)

  • 変換された TNF

    | 0   | 1   | 2   | 3   |
| --- | --- | --- | --- |
| A   | 1RB | 3RB | 1LC | 2LA |
| B   | 2LA | 2RB | 1LB | 3RA |
| C   | 3LA | 1RZ | 1LC | 2RA |

Not Collatz

  • 興味深い点
    • この TM は驚くほど単純
    • Collatz のような規則はない
    • これは Collatz のような Ackermann級 TM が存在する可能性を排除するものではない

Inductive Proof Validator

  • プロジェクトの目標
    • 「帰納的証明」検証器を開発中
    • 標準化された証明書形式を開発し、さまざまな帰納的証明を検証できるようにする
    • まだ初期段階だが、複数の TM の動作を証明することに成功している

GN⁺の見解

  • 興味深い点

    • この記事はチューリングマシンと Ackermann 関数の複雑性を理解するうえで大いに役立つ
    • 単純な規則で複雑な計算を実行できる点が魅力的

  • 批判的な視点

    • この機械の複雑性を理解するには数学的な背景知識が必要
    • 実用的な応用よりも理論的な興味により重点が置かれている

  • 関連技術

    • 帰納的証明検証器は自動化された数学証明システムの開発に大きく貢献しうる
    • 他の複雑な計算問題にも適用できる可能性がある

  • 考慮事項

    • この技術を導入する際は、検証過程の正確性と効率性を考慮する必要がある
    • 複雑な数学的概念を理解して適用するには時間が必要

関連記事

1件のコメント

 
GN⁺ 2024-05-25
Hacker Newsの意見

Hacker Newsコメントまとめ

  • シンプルなチューリングマシンプログラム
    チューリングマシンのプログラムは複雑なスパゲッティコードだと思いがちだが、この新しいプログラムは比較的シンプル。3つの状態（A、B、C）があり、状態BはAとCに制御を渡す一方、AとCは互いを知らず、Bにのみ制御を渡す。これはモジュール的な構造であり、本当のスパゲッティコードなら各状態が他のすべての状態に制御を渡しうる。

  • 興味深い特徴
    このプログラムは空白を出力せず、すべての命令が状態または色を変更する。新しいBB(3,4)の記録保持者は約64ビットの情報を持つ。BBλ(49)は49ビットでグラハム数をはるかに超える。

  • 実装例
    実際にプログラムを実装してみたところ、状態Bは0を2に、1を1に変更してCへ遷移し、状態Cは3を2に変更してAへ遷移する。これにより、3の連続が指数的に長くなる。

  • コードゴルフとの類似
    これらすべてが極端なコードゴルフのように見える。BitGridという個人的な趣味プロジェクトでは、各セルが4ビットの状態しか持たず、4x4グリッドは最大2^64まで数えられる。小さなグリッドでは、端の接続が結果に大きな影響を与える。

  • チューリングマシンの解釈資料の要望
    表をどう読み解くのかについての資料を求める声。チューリングマシンの説明に見える。

  • チューリングマシンの限界
    限られた数の記号で記述できるチューリングマシンの数は有限。一部のチューリングマシンが停止する前にとてつもない数のステップを実行できるという事実に驚かされる。

  • 特別な点の説明要望
    この特定の命令集合がなぜ印象的なのかについて説明を求める声。Ackermann関数級の関数とは何か、実際に何を計算しているのかが気になる。

  • 数学的真理への興味
    一見役に立たない結果のほうが、非常に有用なLLMの発展よりも興味深い。単純な数学的真理に自然と惹かれるからだ。

  • BB(5)とBB(3,4)の比較
    BB(5)はBB(3,4)より大きいのかという質問。bbchallenge.orgではBB(5)は約4700万とされているが、BB(3,4)ははるかに大きいという。

  • 著者による文脈の提供
    著者がいくらか文脈を補ってくれている点がよい。