HN 日本語サマリー

← 一覧へ戻る
科学・技術

13世紀の列挙アルゴリズム、700年間無視される

A 13th-Century Enumeration Algorithm, Ignored for 700 Years (blog.klipse.tech)

6 pointsby viebel0 コメント

要約

本記事は、13世紀のカバラ思想家アブラハム・アブーラフィアが発見した、n文字の単語の全ての順列を体系的に列挙するアルゴリズムについて解説しています。このアルゴリズムは、再帰的な構造を持ち、現代のコンピュータサイエンスにおける再帰アルゴリズムと類似しています。この発見は、17世紀のベルリンガーや1984年の数学者Shimon Zaksの研究とも関連しています。

全文翻訳

700年間無視されてきた13世紀の列挙アルゴリズム

この記事は、カバラ思想家アブラハム・アブラフィア(1240年 – 1291年以降)の著作を研究中に発見したことについてのシリーズの最初の記事です。ツェルーフ(Tserouf)とは、文字を順列化するカバラの技法であり、純粋に数学的な言葉で言えば、n文字の単語のすべての順列の列挙です。

背景

『オル・ハ・セケル』(“知性の光”)の中で、アブラフィアはn文字の単語の可能なすべての並び順を列挙するための体系的な方法を処方しています。この方法は、精神的な実践の枠組みの中で考案されていますが、驚くほど厳密な数学的構造を持っています。

3文字の単語について、アブラフィアはツェルーフ、つまり6つの順列すべての順序を明示的に示しています。

[画像: アブラフィアの順序による、3文字のツェルーフ(順列)]

単語は、最初の文字によって3つのグループに分けられます。

  1. まず、aで始まる単語。
  2. 次に、bで始まる単語。
  3. 最後に、cで始まる単語。

3文字のための2つのルール

アブラフィアは、3文字のツェルーフについて2つのルールを明示的に述べています。

ルール1 — ミラー(鏡像)。 全てのシーケンスは、開始した場所の逆順で終わらなければなりません。アブラフィアはこれを平易に述べています。「最後の発話は最初の発話の逆順である」。最初の単語はabcです。最後の単語はcba、つまり最初から最後まで反転させたものでなければなりません。

ルール2 — ヘッド(先頭)を保持する。 先頭の文字は、それが解放されるまでできるだけ長く保持します。aで始まる全ての単語を列挙し、次にbで始まる全ての単語、次にcで始まる単語を列挙します。先頭は、変更が必要になるまで変わりません。

これらの2つのルールは、3文字の順序全体をほぼ強制するのに十分です。ヘッドを保持するルールは、3つのグループをa、b、cの順に設定します。グループ内では、最後の2文字だけが入れ替わり、ミラー(鏡像)ルールは最初のグループ(abcで始まる必要がある)と最後のグループ(cbaで終わる必要がある)を固定します。

ほぼですが、1つのケースが私を悩ませました。なぜbcaがbacの前に来るのか、その逆ではないのか? 2つのルールからは、それを強制するものは何も見当たりません。

その小さな疑問こそが、この発見全体の原動力です。 時には単純な質問が貴重なものになることがあります。私は数ヶ月間、それを手放すことができませんでした。そして、結果として、それを追いかけることがこのシリーズのすべてにつながったのです。

nからn+1へ: ホイールを回す

3文字の順序から4文字の順序へはどうやって移行するのでしょうか? アブラフィアはもう1つのルールを与えており、それがこの全体の核心です。

最初に戻り、最初の文字を単語の最後に送ってください。

つまり、単語を1ノッチ回転させます。abcdはbcdaになり、cdabになり、dabcになります — 4つの回転、4つのヘッド、4つのグループ。そして、各グループの内側で、残りの文字に全く同じ方法を適用します。

[画像: アブラフィアの順序による、4文字のツェルーフ(順列)]

4つの行はそれぞれ、単語の1つの回転によってヘッダーが付けられており、各行は残された文字に適用された3文字順序の完全なコピーです。

均一なルール

ここにアブラフィアの天才が明らかになります。3文字、4文字、10文字、任意の数に対する全手順は、あらゆるスケールで繰り返し適用される、一つの操作によって支配されています:最初の文字を最後に送る。

この単一の回転が、最上位レベルでグループからグループへとあなたを運びます。それは、残りの文字に適用され、各グループを1レベル下で構築するのと同じ回転です。そして、さらに1レベル下でも同様です。単一のジェスチャーが、順列のネストされた階層全体を歩みます。単語が長くなるにつれて方法はより複雑になるのではなく、単に短いサブワードに同じ動きを再適用するだけです。

これは、コンピュータ科学者が再帰アルゴリズムと呼ぶもの、そして美しく経済的なものです。このルールは述べるのが些細ですが、n!のすべての並び順を、それぞれ正確に一度ずつ生成し、開始点に戻ります。

アブラフィアはこのすべてを、章の最初の行で名前を付けています。

このルールは理解しやすいです。そして、私たちが把握できる終わりはありませんが、それは必然的に終わりを持っています。

3つの節、3つの瞬間:ルールは単純です。それが展開するものは、私たちが心に留めておくことができるどんなものをも超えています。そしてそれでも、その歩みは有限です — それは閉じ、必然的に終わりを持っています。

これを行った他の人々

私が知らなかったのは、その時、どれだけのことがかかっていたかということです。

17世紀まで、アブラフィア以外に順列の順序を与えた人はいませんでした。他のすべての伝統 — 他のすべてのカバラ思想家 — は、単にそれらを表にリストアップしていました。bcaとbacの間のその小さな選択は、世界で唯一の体系的な方法の目に見える先端でした。

歴史的に注目すべき並列が1つあります。規則ベースの方法で全ての順列を走査する規則を独立して発明した唯一の他の人々は、17世紀のイギリスのチェンジリンガー(鐘の鳴らし手)でした。

リンガーたちは鐘楼でその順序を見つけました。アブラフィアはそれを精神的な実践の中で見つけました。異なる世界、同じ目標:順列の全空間を走査し、どれも逃さず、どれも繰り返さない方法。そしてアブラフィアはそれを13世紀に行いました — ベルリンガーより300年早く、コンピュータサイエンスより700年早く。

これがどこへ行くか

したがって、アブラフィアは順列のための本物の再帰アルゴリズムを与えました。それだけでも素晴らしい歴史的な注記となるでしょう。しかし、もっと多くのことがあります。

彼の正確な順序は、1984年に数学者シャイモン・ザクスによって発表されたアルゴリズムと一致することが判明します — これは全く異なる扉を通して到達され、若いビル・ゲイツが彼の唯一の科学論文で研究した動きに基づいています。それが次の記事です。