以前から僕はフローチャートが大好きなのですが、最近いくつかの状況証拠がさらに付け加わって、「計算やアルゴリズム記述の切り札はフローチャートだ」と、ますます強く思うようになりました。
フローチャート大好き
フローチャートが、地味ながらも*1計算科学(computing science)の中心部分に在り続けたことは、「フローチャート大好き」とカミングアウトした次の記事に書いています。
謎の一元体エフイチ(F1)の新しい定式化であるシャイ・ハランのF理論では、直和(双積)とテンソル積を持つ圏をベースにするのですが、これはフローチャート研究の第一人者ステファネスク師匠の半環圏(semiringal category)と同じ概念なのでした。不思議な因縁を感じます。
コンヌとマニン
僕がエフイチを知ったキッカケはコンヌ/コンサニ(Alain Connes and Caterina Consani)の論文Characteristic 1, entropy and the absolute point でした。そのコンヌと、(コンヌと親交がある)マニンは:
「双モノイドの簡単な例 -- 自然数の足し算と余足し算」より:
コンヌ(Alain Connes)やマニン(Yuri Manin)が、最近は計算(computation)やアルゴリズムに興味を持っているようです。場の量子論とかファインマン・グラフなんかと一緒に、原始帰納関数とかルンゲクッタ法とかを話題にしている論文があります。
コンヌ御大(写真左)は1947年4月1日生まれで還暦過ぎてます。マニン(写真右)はコンヌよりさらに10歳年上で1937年2月16日生まれ。御老公と言っても失礼じゃないでしょう。水戸の光圀公(ただしテレビ番組)同様に、マニンも現役*2。コンヌもマニンも歴史に残るであろう大数学者ですが、二人とも数論と物理に深く精通しているところが似ています。
コンヌは1990年代にクレイマー(Dirk Kreimer)と"Hopf algebras, Renormalization and noncommutative geometry" (1998) という論文を書いています。そのなかで使ったホップ代数は現在 Connes-Kreimer Hopf algebra of rooted trees と呼ばれているようです(よく知らんが)。コンヌ/クレイマーの別な論文 "Lessons from Quantum Field Theory" では、数値計算のルンゲクッタ法もホップ代数になるんだ、と書いてあります(サッパリ分からんが)。
去年(2009年)からマックスプランク研究所の御老公マニンもこの分野に関心を持って Renormalization and computation というプロジェクトを始めました。"Renormalization and computation I" の目次は次のとおり。
- 0. Introduction
- 1. Feynman graphs and perturbation series: a toy model
- 2. From Feynman graphs to flowcharts and programming methods
- 3. Bialgebras and Hopf algebras related to computation
- 4. Regularization and renormalization
2章のタイトルから、ファインマン・グラフがフローチャートやプログラミング手法として定式化できることが推測されます。3章のタイトルからどうやら、計算(computation)は双代数(bialgebra)やホップ代数(Hopf algebra)に関係付けられるらしいです。
イオネスク、ヤノフスキー、長谷川
ファインマン・グラフをプログラムの表現、あるいは計算デバイスとみなす方向では、イオネスク(Lucian M Ionescu)という人がファインマン圏(Feynman category)なる概念を提唱しています。イオネスクは、Q++ という量子計算プログラミング言語を設計していたりもします。
マニンがしばしば引用しているヤノフスキー(Noson S. Yanofsky)の "Towards a Definition of an Algorithm" は現代的なフローチャートの理論です。アルゴリズムの分類や同定をしたいというヤノフスキーの動機からは、テキストで記述するプログラミング言語はたいして役に立ちません。
計算やアルゴリズムがフローチャートでうまく記述できるという事実の背後にはトレース付きモノイド圏やコンパクト閉圏があります。このことについては、この分野のパイオニアの一人である長谷川真人(はせがわ・まさひと)さんによる次の2つの資料を読むとよいと思います。
トレース付きモノイド圏の一般化であるトレース付き前モノイド圏については:
- Title: Premonoidal categories and a graphical view of programs
- Author: Alan Jeffrey
- URL: http://fpl.cs.depaul.edu/ajeffrey/papers/premonA.pdf
- Title: Traced Premonoidal Categories
- Authors: Nick Benton, Martin Hyland
- URL: http://www.dpmms.cam.ac.uk/~martin/Research/Publications/2002/bh02.pdf
参考
言及した論文を以下に列挙します。
コンヌ御大がクレイマーと書いている論文。こんなかでルンゲクッタ法にも触れている。
- Title: Lessons from Quantum Field Theory -- Hopf Algebras and Spacetime Geometries
- Autors: A. Connes, D. Kreimer
- URL: http://www.alainconnes.org/docs/lessons.pdf
ルンゲクッタ法がホップ代数(量子群)をなすという話。そのもとは次らしい。
- Title: Runge-Kutta methods and renormalization
- Authors: Christian Brouder
- URL: http://fr.arxiv.org/abs/hep-th/9904014
マニン御老公も繰り込みと計算に注目している。2009年から繰り込みと関連付けて計算(再帰関数とかチューリングマシンとか)を扱いだした。
- Title: Renormalization and computation I: motivation and background
- Authors: Yuri I. Manin
- URL: http://arxiv.org/abs/0904.4921
- Title: Renormalization and Computation II: Time Cut-off and the Halting Problem
- Authors: Yuri I. Manin
- URL: http://arxiv.org/abs/0908.3430
マニン論文から引用されているヤノフスキーのアルゴリズムの話。要するにフローチャート理論だと思う。
- Title: Towards a Definition of an Algorithm
- Authors: Noson S. Yanofsky
- URL: http://arxiv.org/abs/math/0602053
イオネスクの論文をひとつだけ。
- Title: From operads and PROPs to Feynman Processes
- Author: Lucian M Ionescu
- URL: http://arxiv.org/abs/math/0701299
根付き木のホップ代数については:
- Title: Two interacting Hopf algebras of trees
- Authors: Damien Calaque, Kurusch Ebrahimi-Fard, Dominique Manchon
- URL: http://arxiv.org/abs/0806.2238
*1:「日陰の身ながらも」と言うべきか。けど、「フローチャートからマゾ・テストまで」では、アービブ&マナ、ロビン・ミルナー、ダナ・スコットのような大スターにも注目されたのだから「完全に日陰の存在だったかというと、そうでもない」と書いているな。
*2:http://en.wikipedia.org/wiki/Yuri_I._Manin によると、そのお弟子さんが凄まじい; Manin had over 40 doctoral students, including Alexander Beilinson(ベイリンソン), Alexei Skorobogatov(スコロボガトフ), Vladimir Drinfeld(ドリンフェルト), Vyacheslav Shokurov(ショクロフ), Arend Bayer(ベイヤー) and Victor Kolyvagin(コリヴァギン).