Hero Image
イコシアン・ゲームとハミルトン閉路

1856 年、まだ非可換な代数に取り組んでいたハミルトンは、イコシアン算法を発明した。三つの記号 $\iota$、$\kappa$、$\lambda$ が次の規則に従う。 $$\iota^2 = 1, \qquad \kappa^3 = 1, \qquad \lambda^5 = 1, \qquad \lambda = \iota\kappa.$$今日の言い方では、これらは二十の三角形の面をもつ正二十面体の回転群を生成する。ハミルトンは 1857 年にダブリンで開かれた英国科学振興協会の会合でこの算法を発表し、それが正十二面体、つまり十二の五角形の面と二十の頂点をもつ立体の辺に沿った道筋を表すことに気づいた。 パズル このアイデアを広めるため、ハミルトンは十二面体を平たく押しつぶして盤の上に描き、二十の頂点に穴をあけて、それぞれに都市の名をつけ、番号のついた二十本のピンを添えた。課題は、ある都市から出発し、辺だけをたどって、ほかのすべての都市をちょうど一度ずつ訪れ、出発点に戻ることである。1859 年、彼はロンドンのゲーム製造業者ジョン・ジャックス社に権利を 25 ポンドで売った。ゲームは『イコシアン・ゲーム』として、また『旅人の十二面体』という携帯版として売られたが、商業的には失敗だった。少し根気があれば、基本の課題は数分で解けてしまうのだ。 サンパウロ大学数学統計研究所のマテマテカが所蔵するイコシアン・ゲームの複製。番号のついたピンが、二十の頂点をめぐる旅の順序を示している。Estes Objethos Atelier、撮影 Alisson Ricardo · Wikimedia Commons · CC BY-SA 4.0 やってみよう。文字は、ハミルトンが都市の名に使った子音である。 この対話型の図を使うには JavaScript を有効にしてください。議論の全体は本文にあります。 オイラーは解き、ハミルトンは解けない すべての頂点をちょうど一度ずつ通って出発点に戻る道筋は、今日ハミルトン閉路と呼ばれる。この問いは、オイラーがすべての辺をちょうど一度ずつ渡ろうとしたケーニヒスベルクの橋のいとこのように見える。だが二つはまったく違う。辺については、オイラーが 1736 年に簡単な判定法を与えた。各頂点から何本の辺が出ているかを見ればよい。頂点については、簡単な判定法を誰も知らない。1972 年、リチャード・カープはハミルトン閉路問題を NP 完全問題のリストに入れた。これを速く解く方法を見つけた者は、何千もの難問を速く解く方法を手にし、クレイ研究所から百万ドルを得ることになる。 そのいちばん有名な親戚が巡回セールスマン問題である。ある地図のすべてのハミルトン閉路のうち、どれが最も短いか。配達経路、回路基板の穴あけ、DNA の配列決定などに現れる。 カークマンが先だった ハミルトンより二年早い 1855 年、イギリスの聖職者で数学者のトマス・カークマンは、どの多面体がすべての頂点をちょうど一度ずつ通る閉路をもつかをすでに問い、それが不可能な例も示していた。名前は、より有名で、売り物のゲームをもっていたハミルトンのものになった。 練習:辺を数える正十二面体では、20 個の頂点のそれぞれが 3 本の辺に接している。辺は何本あるか。また、ハミルトン閉路はそのうち何本を使うか。 頂点ごとに数えると $20 \times 3 = 60$ 個の辺の端があり、一本の辺には端が二つあるので、$60 / 2 = 30$ 本である。ハミルトン閉路は 20 個の頂点を通って戻るので 20 本の辺を使い、残りの 10 本は使われない。

Hero Image
自己増殖オートマトン

晩年のフォン・ノイマンは、哲学のように聞こえる問いを自らに投げかけた。機械は自分自身の複製をつくることができるか。難しさは論理にある。複製をつくるには、機械は自分自身の記述を必要とする。だが記述は機械の一部なので、記述そのものも記述しなければならず、こうして終わりのない後退に陥る。 記述、構成機、複写機 1948 年からの講演でフォン・ノイマンが示した出口は、三つの部品を分けることだった。 任意の機械 $X$ の記述 $D(X)$ を読んで $X$ をつくる構成機 $A$ どんな記述でも、理解することなく複写する複写機 $B$ 二つをつなぐ制御機 $C$ さて、機械 $A + B + C$ に、それ自身の記述 $D(A + B + C)$ を与える。構成機は記述を読んで新しい機械 $A + B + C$ をつくり、複写機は記述の写しをつくって新しい機械に渡す。結果は、自分自身の記述をもった完全な複製である。後退が止まるのは、記述が二通りに使われるからだ。一度は実行すべき命令として、もう一度は読まずに写すテキストとして。 DNA より前に 1953 年、ジェームズ・ワトソンとフランシス・クリックは DNA の二重らせんを記述した。細胞が行っているのは、まさにフォン・ノイマンが予言したことだった。DNA はリボソームによって読まれてタンパク質がつくられ(構成機)、細胞が分裂するときには解釈されることなく一文字ずつ写される(複写機)。フォン・ノイマンは、生物学が生命のやり方を示すより前に、機械について考えることで増殖の論理構造にたどり着いたのである。 セルの格子 このアイデアを厳密にするため、フォン・ノイマンには機械を組み立てられる単純な「宇宙」が必要だった。ウラムの提案で、彼は小さな正方形からなる無限の格子を使った。各正方形は 29 の状態のどれかにあり、すべてが各ステップで同時に、四つの隣の状態に応じて変わる。この格子の中に、彼はテープを読み、自分自身の複製をつくり、テープを写すことのできる、途方もない数のセルからなる巨大な配置を設計した。この仕事は彼の死の時点で未完成だったが、共同研究者のアーサー・バークスが完成させ、1966 年に『自己増殖オートマトンの理論』という題で出版した。 スタニスワフ・ウラムのロスアラモスの身分証。機械のための宇宙としてセルの格子をフォン・ノイマンに提案したのはウラムだった。Los Alamos National Laboratory · Wikimedia Commons · パブリックドメイン こうした格子は今日セル・オートマトンと呼ばれる。1970 年、イギリスのジョン・コンウェイは、生と死の二つの状態しかなく、規則も一行で済むものを発明した。生きたセルは生きた隣(斜めも数える)が 2 個か 3 個なら生き残る。死んだセルは生きた隣がちょうど 3 個なら誕生する。それ以外は死ぬか、死んだままである。コンウェイがライフゲームと呼んだこの仕組みはきわめて豊かで、その中でも計算機や自己複製する機械を組み立てることができる。 練習:ブリンカーライフゲームで、横一列に並んだ三つの生きたセルは「ブリンカー」をなす。次のステップでそれが縦一列になることを示せ。 真ん中のセルは生きた隣が 2 個なので生き残る。両端のセルは生きた隣が 1 個しかないので死ぬ。真ん中のすぐ上とすぐ下の二つのセルは、生きた隣がちょうど 3 個(横列の三つ)なので誕生する。結果は縦一列の三つである。同じ推論で、次のステップには再び横になり、この模様は永遠に点滅し続ける。

Hero Image
ジョン・フォン・ノイマンの遺産

フォン・ノイマンのような頭脳は、人間より優れた種の存在を示しているのではないかと、私はときどき考えた。 — ノーベル物理学賞受賞者ハンス・ベーテ、ノーマン・マクレイの伝えるところによる この連載の八つの文章は、フォン・ノイマンがしたことの一部を示すにすぎない。完全な一覧は六巻の著作集を埋め、彼の時代の数学のほとんどあらゆる分野にわたっている。 純粋数学 作用素環。 1929 年から 1943 年にかけて、一部はフランシス・マレーとの共同で、今日フォン・ノイマン環と呼ばれる作用素環の理論をつくった。解析学と数理物理学で最も活発な分野の一つである。 エルゴード定理。 1932 年、統計物理学のある原理を正当化する定理の一つの版を証明した。ある量の時間平均は、とりうるすべての状態にわたる平均に等しい、という原理である。 ヒルベルトの第五問題。 1933 年、ヒルベルトが 1900 年に提出した問題の一つ、連続群はどんなときに自動的に「なめらか」になるかという問題の、コンパクトな場合を解いた。 経済、天気、戦略 経済成長。 1937 年に発表され、それより数年前にプリンストンのセミナーで報告された論文で、拡大する経済のモデルを組み立て、ミニマックスと同じ数学で均衡の存在を証明した。数理経済学の基礎となった文献の一つである。 天気予報。 1950 年、ジュール・チャーニーが率い、フォン・ノイマンも加わったグループが、ENIAC で最初の数値天気予報を行った。24 時間の予報に約 24 時間の計算がかかった。今日の天気と気候を予測するモデルは、この実験の子孫である。 核戦略。 冷戦の間、ゲーム理論は軍拡競争を考えるのに使われ、フォン・ノイマンは大陸間ミサイルの計画に加わった。この推論に結びついた「相互確証破壊」という言葉は、今も一つの時代を要約している。 「特異点」という言葉 1958 年、スタニスワフ・ウラムは友人を追悼する文章を書いた。その中で彼は、加速し続ける技術の進歩についての会話を回想している。その進歩は「人類の歴史におけるなんらかの本質的な特異点、それを越えると私たちの知る人間の営みは続きえない点」に近づいているように見える、と。これがこの意味でのこの言葉の、記録に残る最初の使用であり、何十年ものちに人工知能をめぐる議論の主題となった。 ロスアラモスの身分証の写真のジョン・フォン・ノイマン。1940 年代。Los Alamos National Laboratory · Wikimedia Commons · クレジット表記 彼をどう語るか フォン・ノイマンは、今世紀で最も抽象的な数学者の一人であると同時に、科学の軍事応用に最も深く関わった一人でもあり、その二つは彼の物語の中で切り離せない。彼がつくるのを助けた計算機は爆弾を計算するために生まれ、まもなく天気、市場、タンパク質を計算するようになった。ゲーム理論は室内ゲームについての論文から生まれ、核戦略の手引き書や携帯電話の周波数の競売にまで行き着いた。 彼が残した教訓は、分野の境界を尊重しなかった数学者の教訓である。彼は物理学も経済学も計算機も、数学が役に立ちうる場所として扱った。そして数学はほとんどいつも役に立ったのである。 IAS の記憶装置にはどれだけ入ったか 1952 年の高等研究所の計算機は、40 桁の二進数からなる「語」を 1024 個もつ記憶装置を備え、それをブラウン管に保持していた。$1024 \times 40 = 40\,960$ ビット、つまり $5\,120$ バイトであり、この段落があなたの携帯電話で占める容量より少ない。その記憶装置で、水素爆弾の計算、天気予報、生物進化のシミュレーションが走ったのである。 練習:IAS の記憶装置1 ギガバイト($10^9$ バイト)のメモリーカードには、IAS の記憶装置がいくつ入るか。 IAS の記憶装置一つは $5\,120$ バイトである。$\frac{10^9}{5\,120} \approx 195\,000$。今日の小さなカード一枚に、フォン・ノイマンの計算機のほぼ二十万倍の記憶が入る。

Hero Image
アラン・チューリングの遺産

チューリングは機械が考えると信じている。チューリングは男と寝る。ゆえに機械は考えない。 — アラン・チューリング、ノーマン・ラウトレッジへの手紙(1952) 有罪判決の直後にチューリングが友人に書いたこの苦い三段論法は、彼の生涯を要約している。論理で考える人が、彼を理解しない人々に裁かれたのである。しかし、彼が残した仕事はいたるところにある。 計算機科学の中に チューリング機械は今も、計算するとはどういうことかの公式の定義である。計算機科学者が、ある問題には「アルゴリズムがない」と言うとき、それはどのチューリング機械もその問題を解けないという意味であり、ある問題が「難しい」と言うとき、数えているのはチューリング機械に必要な歩数である。 その数え方から、この分野で最も有名な問い、P 対 NP が生まれた。答えを確かめるのがやさしい問題は、どれも答えを見つけるのもやさしいのか。ジグソーパズルを組むのは難しいが、組み上がったパズルを確かめるのはやさしい。この違いが本物なのか、私たちの工夫が足りないだけなのかは誰も知らない。クレイ研究所は、これに答えた人に百万ドルを出すとしている。 1966 年から、計算機学会(ACM)は毎年チューリング賞を授与している。計算機科学のノーベル賞とみなされている賞である。 暗号と統計学の中に エニグマとの戦いは、暗号の安全性は鍵の数ではなく、鍵の大部分を一度に除けてしまう欠陥がないことにあると教えた。現代の暗号はこの教訓から生まれた。そしてデシバンは、I・J・グッドを通じて、ベイズ統計学を科学の中心に呼び戻す助けになった。 生物学と人工知能の中に 形態形成の方程式は、模様の数理生物学という一つの分野全体の土台になっている。そして模倣ゲームは、機械が会話するようになった今も、機械が考えるかどうかをめぐるあらゆる議論の基準である。 マンチェスターのサックヴィル公園にあるチューリングの像。2001 年に除幕された。ベンチに座り、リンゴを手にしている。David Dixon · Wikimedia Commons · CC BY-SA 2.0 名誉の回復 何十年ものあいだ、チューリングの戦時の仕事は国家機密であり、有罪判決は口にされない話題だった。状況が変わりはじめたのは 1983 年、数学者アンドルー・ホッジスの書いた伝記からである。その後、次のことが続いた。 2001 年、大学のそばの公園にマンチェスターの像。 2009 年、イギリス政府の謝罪。 2013 年の国王恩赦と、ほかの有罪者にも恩赦を与えた 2017 年の法律。 彼の誕生日である 2021 年 6 月 23 日に発行された、彼の肖像の 50 ポンド紙幣。 覚えておくこと 1936 年:チューリング機械が計算とは何かを定義し、万能機械がプログラム内蔵式の計算機を先取りする。 1936 年:停止問題がどの機械にも答えられない問いがあることを示し、計算可能数がほとんどの実数に手が届かないことを示す。 1939–1945 年:エニグマの数え上げと欠陥、ボンブ、そしてデシバンを使うバンブリスムス。 1950 年:模倣ゲームが「機械は考えるか」という問いをテストに置き換える。 1952 年:形態形成が、拡散がどのように模様を生むかを説明する。 練習:確かめるのはやさしい誰かが $8633=89\cdot97$ だと言う。確かめる手間はどれだけか。ヒントなしに因数を見つけるにはどれだけかかるか。 確かめるにはかけ算一回でよい。$89\cdot97=89\cdot100-89\cdot3=8900-267=8633$。見つけるには $\sqrt{8633}\approx93$ までの約数を試さなければならない。2 から 89 までの素数は 24 個あり、うまくいくのは最後の一つだけである。何百桁もの数になると、確かめるのは今でも一瞬だが、見つけるのは不可能に近くなる。インターネットの暗号はこの非対称に支えられている。

Hero Image
画像クレジット

歴史的な肖像 クリストフ・ベルンハルト・フランケが 1695 年ごろに描いたライプニッツの肖像は、ウィキメディア・コモンズから取得したもので、パブリックドメインです。コモンズが提供する 960 ピクセルのサムネイルを編集せずに使用しています。 出典ページ。 パブリックドメイン・マーク。 ブログの図 表紙と掛け算 $23\times14$ の説明図はオリジナルの図版です。説明図は計算を説明するもので、歴史上の機械の機構を再現したものではありません。 8 ビット、積の法則の各項、π の級数の和のインタラクティブな図は、このシリーズのために作成しました。本文の例を使えば、JavaScript がなくても計算を追うことができます。 記録 ファイル data/leibniz_imagens.json に、肖像の出典、ライセンス、確認日、SHA-256 ハッシュを記録しています。各テーマの歴史資料は、それぞれの記事の末尾に記載しています。 追加した歴史図版 これらの図版はウィキメディア・コモンズによる。それぞれの出典、ライセンス、SHA-256 ハッシュ値は data/leibniz_imagens.json に記録してある。 ライプニッツの論文の二進法の表(1703): ライプニッツ(1703) · Wikimedia Commons · パブリックドメイン ブーヴェが送った『易経』の卦の図(1701): ジョアシャン・ブーヴェとライプニッツ · Wikimedia Commons · パブリックドメイン ドレスデンのライプニッツの計算機: Kolossos · Wikimedia Commons · CC BY-SA 3.0 『新しい方法』の最初のページ(1684): ライプニッツ · Wikimedia Commons · パブリックドメイン ライプニッツの全トピック · ← ライプニッツの遺産

Hero Image
画像クレジット

歴史的な画像 二つの歴史的画像はウィキメディア・コモンズから取得したもので、パブリックドメインです。コモンズが提供するサムネイルを編集せずに使用しています。 アイザック・ニュートンの肖像、ゴドフリー・ネラー、1689 年:出典ページ · パブリックドメイン。 『プリンキピア』の扉、1687 年:出典ページ · パブリックドメイン。 ブログの図 表紙とプリズムの説明図はオリジナルの図版です。割線、√2 の近似、軌道のインタラクティブな図はこのシリーズのために作成しました。これらは教材であり、手稿の複製でも、ニュートンの実験のシミュレーションでもありません。 記録 ファイル data/newton_imagens.json に、ダウンロードした各画像の出典、ライセンス、確認日、SHA-256 ハッシュを記録しています。各テーマの歴史資料は、それぞれの記事の末尾に記載しています。 追加した歴史図版 これらの図版はウィキメディア・コモンズによる。それぞれの出典、ライセンス、SHA-256 ハッシュ値は data/newton_imagens.json に記録してある。 ウールズソープ・マナー: DeFacto · Wikimedia Commons · CC BY-SA 4.0 ウールズソープのリンゴの木: David Smith · Wikimedia Commons · CC BY-SA 2.0 1668 年の反射望遠鏡の複製: Science Museum Group · Wikimedia Commons · CC BY 4.0 『流率法』の扉(1736): ニュートン著、ジョン・コルソン訳(1736) · Wikimedia Commons · パブリックドメイン アイザック・ニュートンの全トピック · ← ニュートンの遺産

Hero Image
画像クレジット

歴史的な画像と写真 すべてウィキメディア・コモンズによる。コモンズが提供する縮小画像を、圧縮以外の編集をせずに使っている。 16 歳のチューリング、アーサー・レジナルド・チャフィン撮影とされるパスポート写真:出典ページ · パブリックドメイン。 1951 年のチューリング、エリオット&フライ写真館の肖像:出典ページ · パブリックドメイン。 キングズ・カレッジの礼拝堂、Martinvl 撮影:出典ページ · CC BY-SA 4.0。 ブレッチリー・パークの館、DeFacto 撮影:出典ページ · CC BY-SA 4.0。 ローター三つのエニグマ、アメリカ国家安全保障局:出典ページ · パブリックドメイン。 復元されたボンブ、Mike Peel 撮影:出典ページ · CC BY-SA 4.0。 パイロット ACE、Philafrenzy 撮影:出典ページ · CC BY 2.0。 マンチェスターの「ベビー」の複製、Parrot of Doom 撮影:出典ページ · CC BY-SA 3.0。 サックヴィル公園の像、David Dixon 撮影:出典ページ · CC BY-SA 2.0。 大型のフグの皮膚、Chiswick Chap 撮影:出典ページ · CC BY-SA 3.0。 チューリングの模様とチーター、Philip Ball 作成の図:出典ページ · CC BY 4.0。 このサイトで作成した図 表紙、対話型のチューリング機械、反応拡散のシミュレーションは、このコースのために作成した。シミュレーションはグレイ=スコット・モデルを 200×200 の格子で計算したもので、文字を含まないので、サイトのすべての言語で使える。対話型の機械は四つの言語すべてで動作する。 記録 ファイル data/turing_imagens.json に、ダウンロードした各画像の出典、ライセンス、確認日、SHA-256 ハッシュ値を記録している。各テーマの歴史資料は、それぞれの記事の末尾に挙げている。 アラン・チューリングの全トピック · ← アラン・チューリングの遺産

Hero Image
機械のための記法:コンピュータが確かめる証明

二千年のあいだ、数学の証明は人が読むために書かれた文章だった。「明らかな」段階を飛ばしたり、図にたよったり、共同体の約束を使ったりできた。残りは読み手が補ったのである。この五十年で、何ひとつ補わない読み手が現れた。コンピュータである。 四つの色 となりあう国がちがう色になるように地図を塗るには、何色あれば足りるか。答えの四色は 1852 年に予想され、一世紀以上も抵抗した。1976 年、イリノイ大学のケネス・アッペルとヴォルフガング・ハーケンは、問題を二千近くの場合に帰着させ、それをコンピュータに一つずつ、千時間以上の計算時間をかけて確かめさせることで証明した。 四色で塗られた地図。となりあう二つの地域が同じ色になることはない。Inductiveload · ウィキメディア・コモンズ · CC BY-SA 3.0 学界は割れた。人間がだれも全部を読めない証明は、証明なのだろうか。支持する人々は、長い証明の多くもまた、だれにも全部は読まれていないことを指摘した。批判する人々は、プログラムには誤りがありうると言った。2005 年、フランスのジョルジュ・ゴンティエは、コンピュータの部分も含めて証明全体を、Coq という証明支援系で書いた。それは公理から出発して論理の一歩一歩を確かめるものである。疑いは場所を移した。「プログラムは正しいか」ではなく、「確かめる側は正しいか」になったのである。それはずっと小さく、点検しやすいプログラムである。 ケプラー予想 1611 年、ケプラーは、オレンジをもっとも密に積む方法は八百屋のピラミッドだと主張した。1998 年、アメリカのトーマス・ヘイルズは、数百ページの議論と大がかりなコンピュータ計算を組み合わせた証明を発表した。査読者のチームは四年間取り組み、正しさを「99% 確信している」と述べた。ヘイルズは残りの 1% に満足せず、証明全体を形式言語で書く Flyspeck 計画を始めた。2014 年、何十人もの協力者とともに計画は完了した。機械が一歩一歩を確かめたのである。 Lean 今日、数学者にもっともよく使われている証明支援系は Lean で、2013 年に、当時マイクロソフト・リサーチにいたブラジルのレオナルド・デ・モウラが作った。そのまわりに mathlib が育った。何百人もが書いた、数十万の形式化された定理をもつ共同のライブラリである。2020 年、ドイツのフィールズ賞受賞者ペーター・ショルツェは、自分でもすべての細部を確かめたか自信のない自分の結果を形式化するよう、共同体に呼びかけた。「液体テンソル実験」(Liquid Tensor Experiment)は 2022 年に終わった。結果は正しく、形式化によって証明を簡単にできる箇所も見つかった。 Lean の一行は次のようなものである。 theorem soma_comuta (a b : ℕ) : a + b = b + a := Nat.add_comm a b 「任意の自然数 $a$、$b$ について $a + b = b + a$ であり、証明はライブラリの交換法則の定理である。」何ひとつ言わずにすませていない。各文字の型も、各段階の出どころも。これは第7章の線形の書き方を極限まで推し進めたものであり、第4章のことばによる証明を、機械が確かめられる文法に翻訳したものである。 共同体を変える記法 形式化は仕事のしかたを変えつつある。2024 年にイギリスのケヴィン・バザードが始めたフェルマーの最終定理の形式化のような計画には、会ったこともない何十人もの協力者が集まり、それぞれがひとつの補題を形式化する。継ぎ目は機械が確かめるので、部品はきっと組み合わさるという確信がある。記法はまたしても、だれがどのように参加できるかを決めている。

Hero Image
命令する等号:x = x + 1 とプログラミング言語

数学者にとって、 $$x = x + 1$$という一行は解のない方程式である。両辺から $x$ をひくと $0 = 1$ が残る。プログラマーにとっては、もっともよく出てくる行のひとつで、「$x$ の値をとり、一を足し、結果を $x$ にしまえ」という意味である。同じ記号が、二つの共同体で正反対の仕事をしている。あちらでは等しいことを主張し、こちらでは代入を命じるのである。 Fortran が等号を選んだ 張本人は Fortran である。広く使われた最初の高水準プログラミング言語で、ジョン・バッカスの率いるチームが IBM で作り、1957 年に公開された。プログラムはパンチカードに打ちこまれ、一枚に一文で、カード穿孔機のキーボードには記号が少なかった。「$N$ に値 $27$ をしまえ」と言うために、Fortran は技術者の式のように N=27 と書いた。 Fortran の文が打たれたパンチカード。二枚めのカードの N=27 は、N が 27 に等しいと主張しているのではない。N に 27 をしまえと命じているのである。Tangopaso · ウィキメディア・コモンズ · パブリックドメイン この選択は実用的なもので、そのまま定着した。しかし、プログラミングを数学として考える人々は落ち着かなかった。1958 年から 1960 年にかけて国際委員会が作った Algol 言語は、代入には別の記号 := を使い、= は比較のためにとっておいた。スイスのニクラウス・ヴィルトは Pascal(1970)で := を引きつぎ、ドナルド・クヌースは『The Art of Computer Programming』で代入を矢印 $x \leftarrow x + 1$ で書く。アイバーソンの APL も矢印を使い、統計言語 R はそれを <- として受けついだ。

Hero Image
思考の道具としての記法:アイバーソン

1962 年、ハーバードで教えたのち IBM で働いていたカナダのケネス・アイバーソンは、『あるプログラミング言語』(A Programming Language)という本を出版した。題名に反して、それは数学の記法の本だった。数のリストや表をまるごと扱う演算のための新しい記号を使って、アルゴリズムを簡潔かつ正確に書く方法である。数年後、IBM 自身がこの記法をコンピュータで実行できる言語に変え、本の名をとって APL と名づけた。 床、天井、そしてかっこ アイバーソンの記号のいくつかは、APL を出てふつうの数学に入った。もっともよく知られているのは、床関数と天井関数の組である。 $$\lfloor x \rfloor = x \text{ 以下の最大の整数}, \qquad \lceil x \rceil = x \text{ 以上の最小の整数}.$$彼以前は $[x]$ や「$x$ の整数部分」と書かれ、天井関数の記号はなかった。二つがあれば、いくつもの場合分けが必要だった計算が一行に収まる。$1$ から $100$ までの $7$ の倍数の個数は $\lfloor 100/7 \rfloor = 14$ である。 もうひとつの記号、アイバーソンの括弧は、命題を数に変える。 $$[P] = \begin{cases} 1, & P \text{ が真のとき}, \\ 0, & P \text{ が偽のとき}. \end{cases}$$これを使えば、「$1$ から $n$ までの偶数を数える」はふつうの和 $\sum_{k=1}^{n} [k \text{ は偶数}]$ になり、その和はいつもの規則で扱える。ドナルド・クヌースは 1992 年に『記法についての二つの覚え書き』(Two notes on notation)という論文でこの括弧を擁護し、ロナルド・グレアム、オーレン・パタシュニクとの共著『コンピュータの数学』(Concrete Mathematics)の全体で使った。前の文章のクロネッカーのデルタは特別な場合にすぎない。$\delta_{ij} = [i = j]$ である。