Length3
24 min read

27バイトの激キショVMから、観測だけでrankを得る並列u32基数ソートを構成しよう

27 バイトのアーティファクトをデコードした subleq 変種 VM を、feed/read の観測だけで最小オートマトンへ商化する。遷移半群が right-zero になるので状態の受け渡しなしにバイト列を並列処理でき、観測された byte rank がそのまま u32 基数ソートを正当化する。

27 バイトが、並列化の面倒を全部持っていってくれた話である。

27-byte artifact
    ↓ decode
激キショVM
    ↓ complete future
最小オートマトン
    ↓ erase VM
普通の表引き

1000 個のワーカーに、200 KB のバイト列を勝手に分割して投げる。各ワーカーの初期状態はわざとデタラメにする。ワーカー同士の通信は無し。チャンク境界の調整も無し。初手で何のことやら、と思うだろうが正解なんで、ちょい待ち。

   1 workers, each started from a BOGUS state: matches serial = True
   3 workers,                        ...       True
   8 workers,                        ...       True
  64 workers,                        ...       True
1000 workers,                        ...       True

各ワーカーが自分のチャンクから生成した出力列をチャンク順に連結すると、全体を先頭から逐次処理した出力列とバイト単位で一致する。初期状態は全部間違っているのに。

Codex 曰く、これは任意の有限バイト列、つまり Byte* 全域で成り立つらしい。証明を見る限り合っている。だが俺が即座に信用しないほうが健全だし、少なくとも読者も信用していないだろう。なのでファズったらマジで通った。頭を抱えた。

これは、我ながらホンマか？ 確かめてみるぞというスクラップである。

0. なぜこれが欲しいのか

独自codecで27バイトへ詰めた疎VM像
  ↓
モード依存トラップ付き減算VMで実行
  ↓
feed/read以外を隠蔽
  ↓
完全未来を総列挙
  ↓
最小商と区別suffixを構成
  ↓
具体VMを消去
  ↓
256状態・遷移行1本のindex
  ├─ 任意長履歴の厳密キャッシュ
  ├─ 通信不要のストリーム並列化
  ├─ 決定的な並列subset還元
  └─ 観測からrankを得るu32基数ソート

待て待て。そもそも最初に欲しかったのは並列化ではない。

任意長の履歴に対して使えるキャッシュが欲しかった。ここでいう「無限ヒストリー」は、一本の無限列を食わせるという意味ではなく、長さに上限のない有限履歴全体、つまり Byte* が無限集合だという意味だ。

その履歴空間が、どうも 256 状態に抑えられるっぽい。

この時点では下限まで証明するとは言わない。だが、何かこれ KV キャッシュに使えそう……となった（ALiBi 使えばいける）。そのうえで、バイト列を舐める状態機械を並列化しようとすると、だいたい次の壁に当たる。

壁 1: 位置 i の状態は 0..i−1 の全部に依存する

素直に書くと逐次実行しかできない。 定石は遷移モノイド上の parallel prefix scan だ。バイト列をチャンクに割り、各チャンクの「状態 → 状態」の写像を計算し、結合律で畳む。だがこれは 256 要素の遷移関数を合成する木を組むということで、span は O(log n)、各ワーカーは部分結果を受け渡す必要があり、ワーカー数を変えるとチャンク境界が変わって受け渡しの形も変わる。実装は普通に面倒だし、境界のバグは再現しにくい。まあ妥当。

壁 2: メモ化のキャッシュを何個確保すればいいか分からない

履歴をキーにして計算結果を憶えたい。だが「履歴 → 状態」のキー空間は履歴長に対して指数的だ。実務では適当に上限を切って LRU で回し、ヒット率を測って調整する。厳密性の保証は無い。 近似が入っているのか入っていないのか、コードを読んでも分からない。まあ、これから出す構成もコードを読んで即座に自明感があるかと言われると無い。誰かしらが良い感じに再現してくれるやろ、で先に進む。

壁 3: 並列還元は完了順序で結果が変わることがある

エンジニアは bithack という飛び道具で無茶した後に、避けられない O(n) を並列化する生き物である。ワーカー数やスケジューリングを変えると出力が微妙に違う。run ごとに結果が揺れるバグのデバッグは、控えめに言って人生の無駄だ。ちな俺は、都合の良い codec を作るのに 4 か月溶かした。

欲しいもの。 これら 3 つが「測ってみたら大丈夫だった」ではなく証明付きで保証されている状態。しかもその保証が、小さくて検査可能な対象に集約されていること。あとこう、週間リミットが切れて気合で記事を書いたからには AI スロップ叩きに臆せず、AI による語彙の丸め込みと抽象化に屈せず、ship する気持ちが欲しい。

この記事は、それが 27 バイトに集約されていた、という話だ。

1. 何を探索したのか

個人的にこねている変なプロジェクトがあって、その副産物として出てきた。探索そのものは単純で、subleq の変種の空間を、次のキーで辞書順最小化しているだけ。ここは普通に恣意あるけど、経験的にメモリが小さいほど反例集合を潰しやすい気がする。俺は Rust の HashMap に泣かされたので、少なくとも定数倍の重さは信用している。競プロも GPU も詳しくないが、文字列を UTF-8 のまま富豪的に舐めるか、触る bit を減らすかの勝負になるなら、フロンティアラボの連続メモリを直接舐められる表現は地味すぎて最後まで出てこなさそうだから、本質はたぶんメモリの安さにある筈。

(critical span, total work, code length, rank)

第 1 キーが critical span。第 2 が total work。code length は 3 番目。ここは後で効いてくるので憶えておいてほしい。

そして探索は source-blind——「何のための機械を作っているか」を知らされていない。ここは pKt っぽいって意味で使っているので nit は勘弁。制約を満たす物理表現を、上のキーで最小化するだけ。出てきたのがこれ。

CODE = bytes.fromhex("80c68460ca148529482e4891069c883a48a40809932e3e07840f4c")
CODE_SHA256 = "542e81ea171b6efe882585184d88e2a117748627de4016285fd584e984306c1a"

ビット列としてほどくと VM イメージが出る。

ここで「artifact と VM が密結合しすぎやろ！」という文句が聞こえる。一関数に隠蔽したいのは同意。今は進もう。

命令は dst -= src して結果が正なら次へ、そうでなければ branch へ飛ぶ、の一種類だけ。branch が負のときだけ、モードに応じて「1 バイト出力」か「状態のコミット」として解釈される。非ゼロなセルは 17 個。

read_entry = 50
feed_entry = 20
support    = 20..34 (feedルーチン) + 50,51,52 (readルーチン)

重要なのはここから先だ。 以降このコードの構造は一切参照しない。触るのは 2 つの窓だけ。

  • feed(image, byte) -> image — 1 バイト食わせて次の状態を返す
  • read(image) -> byte | None — 現在の状態から 1 バイト観測する

この 2 つだけで状態機械としての完全な未来を列挙し、商を取る。

有限決定的な残余系 (S, output, step) に対して s ~ t ⟺ 任意の有限バイト列 h について output(step*(s,h)) = output(step*(t,h))

これは right congruence になり、出力による分割から始めて 256 個の後続のラベルが一致するまで細分化すれば S/~ に到達する。Myhill–Nerode と Moore の分割精密化そのものだ。

これを一言で丸めるまでには長すぎる経緯があるが、無慈悲に省略される。

（脱線、これを元に Byte* 全域を覆っているならマイヒルを曖昧な自然言語に拡張できるんでは？ って気づいた読者はかなり賢いと思うし、多様な反例を含むデータと外側の学習専用機があれば Yes の筈。誘導がないと無理だけど。）

商を取った結果がこうなった。

$ python physical-minimum-subset-20260802.py
code_bytes=27 future_states=256 minimum_state_bits=8 physical_rows=1
right_congruence=proved completeness=proved minimality=proved parallel_subset=proved
history_keys=65536->256 exact_cache=ok stable_radix_u32=20512/20512

physical_rows=1。これが冒頭の 1000 ワーカーの正体だ。順番に解いていく。

2. 開けた: feed は 5 命令、read は 1 命令

VM に計装を入れて実行トレースを取った。

使った VM も、よく見ると SUBLEQ より高速化・並列化しきっていて、

  • 命令が減算一種類
  • 負の branch だけモード依存トラップ
  • read モードでは書込みをコミットしない
  • 値ゼロのセルは support から消える

という激キショ仕様なので、皆んなも、これでプログラミングしよう！

feed（入力バイト = 200）

pc=20  mem[1] (0)   -= mem[1] (0)     ->  0       出力レジスタをゼロ化
pc=23  mem[2] (0)   -= mem[2] (0)     ->  0       スクラッチをゼロ化
pc=26  mem[2] (0)   -= mem[0] (200)   -> -200     符号を反転して取り込む
pc=29  mem[1] (0)   -= mem[2] (-200)  ->  200     戻して転写
pc=32  mem[3] (0)   -= mem[3] (0)     ->  0       branch=-2 -> COMMIT

減算しか無い機械なので、値を写すには一度符号を反転して引き算し直す。3・4 命令目がそれだ。式変形と逐次代入で追える範囲。

5 命令目 mem[3] -= mem[3] は何も計算していない。自分自身を引いて必ず 0 を出し、非正なので branch へ落ち、その branch が -2 だからコミットに捕まる。これが halt だ。減算しか無い機械で「止まる」を書くとこうなる。

read

pc=50  mem[61] (0) -= mem[60] (0) -> 0     branch=-1 -> EMIT mem[1] = 200

1 命令。同じ手口だ。番地 60 と 61 は永久にゼロのまま放置されたセルで、引けば必ず 0、非正、branch が -1 なので「mem[1] を出力せよ」のトラップに落ちる。read ルーチンは計算をしていない。意図的に失敗して出力トラップに飛び込むためだけに存在する。

全入力・全深さで命令数を測る。

feed steps @depth0: {5}
feed steps @depth5: {5}
read steps        : {1}

分岐しているように見えて着地点は常に同じ。入力が 0 でも 255 でも、履歴が 0 バイトでも 5 バイトでも、feed はきっかり 5 命令、read はきっかり 1 命令。

3. 仕掛け: 使う前に、必ずゼロにする

書き込まれる番地を全入力について集計する。

written addresses: [1, 2, 3]
program region 20-34, 50-52 written?: False

プログラムは自分自身を一切書き換えない。そして決定的なのはここだ——

このルーチンは、読む前に必ずゼロにしている。

1 命令目が mem[1] を、2 命令目が mem[2] を、5 命令目が mem[3] をゼロにする。feed が参照する値のうち、前の状態から持ち越されるものは mem[0]（入力）しかない。

これがどれだけ意図的かは、VM のコミット処理を見ると分かる。

committed = base.copy()
committed.update(overlay)

overlay を丸ごとコミットしている。 マスクもホワイトリストも後始末パスも無い。実行中に書き換えたセルは全部そのまま次の状態に持ち越される。減算の作業セルを潰せば残骸は永久に残る。普通はそうなる。

実測。

b=1   のとき rootとの差分: (0,1) (1,1) (2,-1)
b=200 のとき rootとの差分: (0,200) (1,200) (2,-200)
6回 feedした後の差分:      (0,1) (1,1) (2,-1)     ← 蓄積ゼロ

差分は常に番地 0, 1, 2 の (b, b, −b) だけ。深さをいくら増やしても増えない。残骸を持ち越さないのではなく、そもそも残骸を作らない。

この 27 バイト、VM を本当にウキウキで KISS 原則でやろう、と意気込んだ挙句に出てきたものだ。pKt の実用化イケるやろ、と試してみた結果がこれなので、コルモゴロフは泣くだろ。

これで数字が全部繋がる。

出力理由
到達集合が 256 でちょうど閉じる残骸があれば 256×k に膨れるか発散し、len(states) > 4096 ガードに当たっていた
具体状態 256 = Nerode 商 256履歴が状態に残らないので、具体表現に冗長性が存在しない（併合ゼロ）
physical_rows = 1遷移が現在状態に依存せず、入力バイトのみで決まる
byte_rank = identity符号反転が往復するので、出た値は入力そのもの

4 つの独立した観測に見えたものが、「使う前にゼロにする」1 点の帰結だった。

4. 測った: 頼んだ span 3 と、頼んでいない span 1

ここが本題。

命令レベル: work 5 / span 3 —— これは頼んだ結果

実行トレースからデータ依存 DAG を組む。

i1  mem[1] -= mem[1]      depth 1
i2  mem[2] -= mem[2]      depth 1
i3  mem[2] -= mem[0]      depth 2
i4  mem[1] -= mem[2]      depth 3
i5  mem[3] -= mem[3]      depth 1

work = 5   span = 3   parallelism = 1.67
levels: d1: [1, 2, 3]  |  d2: [2]  |  d3: [1]

depth 1 に 3 命令が並列で立つ。 出力レジスタのゼロ化、スクラッチのゼロ化、そして halt。互いに依存していない。実際の逐次鎖は ゼロ化 → 符号反転 → 戻す の 3 段だけ。

この VM、許可した初期・終了条件、セル利用規約からなる探索空間では、span 3 が下限になる。subleq で符号の正しいバイト転写をするには、(a) 中間セルをゼロにし、(b) そこから入力を引いて負値を作り、(c) それを出力レジスタから引き戻す。この 3 段は連鎖する。コードはその下限を達成したうえで、残り 2 命令を depth 1 に押し込んでいる。

ここまでは、まあ、そうだろう。第 1 キーが critical span なんだから、探索がそこを削るのは当たり前だ。頼んだものが出てきただけ。

ストリームレベル: span 1 —— こっちは頼んでいない

physical_rows = 1 を代数の言葉に直すと、こうなる——

各バイトが定数写像として作用する。

入力 a の後に b を与える作用を f_b ∘ f_a と書けば、

f_b ∘ f_a = f_b

空語を除く遷移半群が right-zero になる。合成すると後ろの入力だけが残る。

したがって位置 i における状態は byte[i] だけで決まり、それ以前の履歴を一切参照しない。壁 1 が消える。

普通の DFA を並列スキャンするには log 深さの木が要る、と書いた。ここでは木が要らない。

=> parallel prefix over the transition semigroup needs NO tree:
   span = 1, work = n, inter-worker state handoff = 0 bytes

証拠として 20 万バイトのストリームを分割し、各ワーカーに意図的に間違った初期状態を渡した（(w * 37 + 111) % 256、ワーカーごとに全部違う値）。handoff も同期も無し。

   1 workers, each started from a BOGUS state: matches serial = True
   3 workers,                        ...       True
   8 workers,                        ...       True
  64 workers,                        ...       True
1000 workers,                        ...       True

全部一致。初期状態が何であろうと、最初の 1 バイトで正しい状態に叩き込まれるから、間違えようがない。

ここが †聖杯† ポイントだ。 探索キーに入っていたのは命令 DAG の critical span だ。「バイト列上の parallel scan の span を 1 にしろ」なんて一言も言っていない。頼んでいない。それでも出てきた。

命令レベルの span を削る圧力が、状態の持ち越しを削り、持ち越しが無いことが遷移半群を right-zero にし、right-zero だから prefix scan の木が消えた。下の層で span を削ったら、上の層の span まで 1 に落ちていた。

はい、自明な構成を得たので勝ち。並列プレフィックスの実装、要りません。

5. 4 つの層が、同じ 1 つの事実だった

層現れ方
アセンブリ使う前に必ずゼロにする
オートマトンphysical_rows = 1
代数非空遷移半群が right-zero、各バイトが定数写像
並列span 1、状態 handoff 0、初期状態がデタラメでも正しい

上から下まで全部同じことを言っている。27 バイトの中の mem[2] -= mem[2] という 1 命令が、1000 ワーカーが同期せずに走れる理由になっている。 アセンブリの 1 行と並列スケーラビリティが直結する経験はそう無い。

6. 壊した: 216 ビット全部ひっくり返す

どのくらい際どい所に立っているのか知りたくなって、27 バイトの全 216 ビットを 1 つずつ反転して分類した。

decode_fail          149  (69.0%)   正準符号化の検査で弾かれる
no_output             33  (15.3%)   readが出力トラップに落ちない
vm_fail               20  ( 9.3%)   VMがfailする
SURVIVES              10  ( 4.6%)
closure_blowup         2  ( 0.9%)   状態が4096を超えて発散
not_permutation        2  ( 0.9%)   byte rankが全単射にならない

95.4% が即死。 1 バイト代入変異（27 × 255 = 6885 通り）だと 99.71% が死ぬ。

面白いのは生存者 10 個で、全員に説明がつく。しかも解剖から予測できていた。

9 個は番地 50 と 51——read トラップのダミー被演算子だ。60→44、60→56、61→45、61→53 と散らばっているが、引いて非正になる常時ゼロの番地ならどれでもいいので当然生きる。設計上フリーなパラメータだった。

残り 1 個は番地 33、halt 命令 mem[33] -= mem[33] の dst が 3→2 に変わったもの。mem[2] -= mem[3] になるが mem[3] は 0 なので mem[2] は変化せず、非正のまま branch=-2 に落ちる。別解の halt だ。

生存者は全員「read トラップの自由度」か「halt の自由度」であって、値の転写に効いている命令を触ると 100% 死ぬ。 予測が当たったのは気持ちよかった。

7. 縮めた: 第 1 キーが効いている現場

まじかー、逆符号化器も書くか、ということで decode_image / unpack の逆を実装した。往復を確認。再現スクリプトは AI で再現してください。

round-trip reproduces CODE exactly: True

これで任意のイメージをバイト列に戻せる。解剖から 2 つ気づいていた——read トラップの被演算子はゼロでよく（Image.from_memory は値ゼロのセルを support から落とす）、プログラムはレジスタ 0–3 の直後まで降ろせる（gap 符号化はアドレス差に課金する）。総当りした結果、20 バイトで完全な未来が 256×256 の遷移表までバイト単位で一致するコードが出た。

7 バイト短い。だが code length は第 3 キーだ。短いだけでは勝てない。第 1 キーで殴られていないか確かめる。

code       feed  read  total  conflict  critical span   len
           w/s   w/s    work    (regs)
27-byte    5/3   1/1      6     none      3  (∥)         27
23-byte    5/3   1/1      6     none      3  (∥)         23
20-byte    5/3   1/1      6      [0]      4  (;)         20

殴られていた。

20 バイト版の read は mem[0] -= mem[0]——入力レジスタを書き潰す。書き込む値は 0、そこには b が入っている。破壊的だ。したがって read を feed と並行に走らせられない。直列化するしかない。critical span が 3 から 4 に伸びる。

対して 27 バイト版は mem[61] -= mem[60]、両方とも死んだセルで、書き込む値も 0 で元から 0。メモリをビット単位で不変に保つ観測だ。feed と並行に走る。span 3 のまま。

27-byte -> (3, 6, 27, ...)
20-byte -> (4, 6, 20, ...)

辞書順で勝負にならない。7 バイト短いコードは、第 1 キーで即死する。

しかもこの罰則は、VM の意味論にも命令数にも現れない。VM は read モードでコミットしないので、テストは両方通る。Rust で共有メモリにスナップショット無しで載せた瞬間に初めて差が出る。探索キーが、テストが検出できない性質を先に潰していた。

そしてこれには副産物がある。20 バイト版を差し込んでも、キャッシュ下限も並列還元もソートの licence も全部そのまま動いた。この構成は「artifact を読まない、タスク固有の演算表を持たない、観測窓ふたつしか触らない」という規律の上に立っている。完全な未来さえ同じならコードが違っても下流は一文字も変わらない——その主張が実験で確かめられた形になった。対象は正準だが、コードは一意ではない。

8. 上に乗るもの

壁 2 と壁 3 に戻る。

壁 2 → 下限が証明された完全未来キャッシュ。 検査用に選んだ 65,536 本の 3 バイト履歴が、完全未来クラスをキーにすると 256 エントリに畳まれる。さらに physical_rows = 1 なので、任意の非空履歴は末尾バイトだけで 256 クラスに落ちる。近似ゼロ。そしてこの 256 は測定値ではなく、任意の未来依存計算に再利用可能な完全未来キーの下限だ。

最初は「256 に抑えられるっぽい。何か KV キャッシュに使えそう」程度だったのが、最後には下限まで付いた。

異なる商クラスに同じ値を割り当てれば、それらを区別する有限 suffix が、一つの値から二つの出力を要求してしまう。

だから、完全な未来を区別する汎用的な厳密キーを、これより小さくすることはできない。「測ったら 256 で足りた」ではなく「256 が下限で、かつ達成可能」と言える。キャッシュ容量が経験則ではなく定理として出る。

壁 3 → 実装前に確定したスケジュール非依存性。 候補に (class, physical_key, source_index) という全順序キーを与え、クラスごとに最小を残すと、

summary(A ∪ B)[q] = min(summary(A)[q], summary(B)[q])

全順序上の pointwise min は結合的・可換・冪等なので、どうチャンク分割しても、どの順で完了しても、何回マージしても直列と 1 ビットも違わない。

検査は 6 要素・3 ワーカーについて、全 source order 6! と、全割り当て × 全マージ順 3^6 × 3! の二つの有限族を総当りしている。一般証明が本体で、これは実装が定理どおりかを確かめる有限検査だ。その後 4908 要素・最大 16 ワーカーの乱択でも確認。Rust の並列実装に降りる前に、これが終わっている。

おまけ: 観測が licence になっているソート。 観測された 1 バイト未来が 0..255 の全単射なら、そのまま digit の rank に使える。observable_byte_rank は全単射でなければ ValueError を投げる。前提が仮定ではなく検査だ。 通れば 4 パスの LSD 基数ソートが正当化される。

20512要素（うち512は重複）→ sorted()と完全一致、同値要素の元順序も保存

変異実験で not_permutation が 2 件出ているのは、その門が実際に閉まるという証拠でもある。

そして信頼しなければならないものの総量。

  • 27 バイト（sha256 固定、正準符号化を 3 条件で強制）
  • デコーダ + VM（100 行未満）
  • 二つの定理と、その有限反例空間を潰す実行可能検査

これだけ。ソートの rank 前提を信頼する必要がない。 digit rank はコードの完全な未来から再構成され、その全単射性は実行時に検査される。LSD 基数ソート本体は、sorted() との一致と安定性で別途検査する。

9. 正直な但し書き

  • 23 バイト版がまだ落ちていない。 上の表の中段。read は純粋、レジスタと衝突なし、span 3、work 6——つまり (3, 6, 23, ...) で 27 に辞書順で勝ってしまう。残る差は配置（元は feed=20 / read=50 で間に 15 セルの空き帯、23 バイト版は feed=4 / read=19 で隣接）と、トラップ被演算子が相異なるか同一かの 2 点。ただし、23 バイト版が落ちる理由は、現在使っている論理 DAG 上の critical span からは出ていない。キャッシュライン共有まで数えるなら、それを別の物理コストモデルとして明示する必要がある。
  • 定理そのものは古典だ。 完全な未来による商は Myhill–Nerode、細分化は Moore（1956）、min 還元の決定性は可換冪等モノイドの標準的性質。新しいのは定理ではなく、それを 27 バイトの対象に集約して実行可能に検査した構成のほうだ。
  • n = 1。 「命令レベルの span を削ったらストリームレベルの span まで 1 に落ちた」は、この一例で観測された話でしかない。

10. 次

  • 健忘症は探索の不変条件か、この一例の幸運か。 critical span を第 1 キーに置くと系統的に「使う前にゼロにする」コードが出るなら、それは 27 バイトについてではなく探索についての主張であって、はるかに強い。命令の span を削ると並列スキャンの span がタダで付いてくる、という話になる。
  • physical_rows > 1 のケース。 right-zero は最も浅い構造だ。span が 1 でなくなる所で、キャッシュとスキャンがどこまで保つか。
  • critical span の定義を物理側まで降ろす。 23 バイト版が落ちるかどうかは、たぶんそこで決まる。

11. おまけ

27 バイトを正規化するとこうなります。

typedef uint8_t state_t;

static inline state_t feed(state_t state, uint8_t byte) {
    (void)state;
    return byte;
}

static inline uint8_t read_state(state_t state) {
    return state;
}

static inline uint8_t rank_byte(uint8_t byte) {
    return byte;
}

static inline uint8_t digit(uint32_t value, unsigned pass) {
    return (uint8_t)(value >> (pass * 8u));
}

コードは gist。依存ゼロ、単体で走る。

python physical-minimum-subset-20260802.py          # 証明とfuzz検査
python physical-minimum-subset-20260802.py 3 2 1 0  # u32をソート

解剖・span 測定・変異・探索のスクリプトも出せる。指摘・反論歓迎、特に「その定理はこの論文で既出」系は大歓迎。

0% read
— left
24 min total