あみだくじが無限ループしないことを証明した

どんなあみだくじでも答えにたどり着くことを証明した。

ここでいうあみだくじとは

20250310_221443794

  • 有限本のくじ(縦棒)がある
  • 縦棒上の点と点を結ぶ横道が有限本ある
  • 横道は水平線だけじゃなく、遠くのくじへ行ったり自身を上に行ったりできる

ダメなこと

  • 「ふりだしへもどる」はない
  • 同じ点と点を結ぶことはできない
  • 一方通行はない
  • 一度通ると崩れるマリオのブロックみたいな道はない
  • どちらに行くか選べる分岐みたいなのはない

なぜ証明したか

PPLで話題になって証明しようかなと思った。

ざっくりとしたアイディア

あみだくじを形式的に定義するアイディア

20250310_233444598

くじ(縦棒)の集合があったとき、横道の集まりで一つのあみだくじのデータを表現した。

例えばこのあみだくじは A0--B2, A1--B0, B1--C0 という3本の横道として表現する。横道は端点のペアであり、端点の添字は点の高さで上から順に一つづつ大きい数字になる。各くじにおいてあみだくじの点から点へ進む関数を適用できなくなるまで行い、点の履歴をくじの結果とする。

停止性を証明するアイディア

通った縦棒の区間に色をつける。一番上から始めた場合、二度と同じ縦区間は通らない。同じ縦区間を通ろうとするなら、一つ前の縦区間も同じである必要があるが、一番最初の縦区間は2度と通れないからである。縦区間の総量は有限なので、ぜったい停止する。

次の2つの性質を証明し、無限ループしないことを証明した。

  • 最初の縦区間は最初にしか通らない
  • ある縦区間を通ったならその直前に通った縦区間はただ一つ定まる

Rocqによるあみだくじの形式的定義

定理証明器Rocq1 (旧Coq) を使って形式化した。

(* くじ上を結ぶ線を両端の位置のペアとして定義 *)
Definition Bypath := (Pos * Pos)%type.

Definition AmidaP (bs: list Bypath): Prop :=
  (* 同じPosは2回現れない *)
  (let '(ps1, ps2) := split bs in NoDup (ps1 ++ ps2))
  (* 各くじで節のmaxがあって、全部の節が含まれる *)
  /\ forall kuji i, Fin.lt i (vpos_of_nat height_ (vmax_ bs kuji)) ->
                PosIn (kuji, i) bs.

Definition Amida := {bs : list Bypath | AmidaP bs}.

あみだくじ上の走査アルゴリズム定義

(* Posの一回分の移動 *)
Definition next pos : option Pos := ...

(* next関数を再帰的にNoneになるまで適用する関数,
   停止性がこの段階で明らかでないので再起回数の上限fuelを設置している *)
Fixpoint run fuel pos : list Pos :=
  match fuel with
  | O => []
  | S p => match next pos with
           | None => [pos]
           | Some pos' => pos :: run p pos'
           end
  end.

証明したこと

Definition init (kuji : Kuji) : Pos := (kuji, F1).

Theorem main: forall amida kuji,
  exists fuel, Finished amida (run amida fuel (init kuji)).

謝辞

ここでの証明は id:KeisukeNakano さんに口頭で説明してもらった証明を形式化しただけなんです。 また、そもそもこの話題は id:ku-ma-me さん, @Seasawher さんから始まりました。 Rocq(Coq)を使った定式化について @tanaka_akr に一緒に議論していただきました。 皆さんに大変感謝します。

Appendix

ソースコード全体: https://github.com/yoshihiro503/rocq-amidakuji

以下参考文献