
注 G [ a ]は、伝統的にエイダ・ラブレスに帰せられるコンピュータアルゴリズムであり、チャールズ・バベッジが設計した仮想解析エンジンを使用してベルヌーイ数を計算するように設計されました。
このアルゴリズムは、「A」から「G」とラベル付けされた一連のメモの最後のもので、チャールズ・バベッジの解析機関に関する唯一の講義をルイージ・メナブレアが1842年にフランス語で書き起こしたものをラブレースが英語に翻訳した際の視覚補助として使用されました。[ 1 ] [ 2 ]彼女の翻訳は、解析機関の可能性に関する彼女の重要なメモとともに、1843年に出版されました。[ 3 ] [ 4 ] [ 1 ]
バベッジは1864年の回想録で、ラブレースと共に様々な音符の作成について論じており、その中には「G」音符も含まれている。彼はベルヌーイ数の計算のための数式を提供し、エイダはそれを解析機関のための手順表に変換した。彼女はまた、彼のためにバグを発見した[ 5 ]。
私たちは、どのような例を用いるべきかについて話し合いました。私はいくつか提案しましたが、最終的な選択は完全に彼女自身に委ねられました。様々な問題の代数的な解法も同様で、ただしベルヌーイ数に関する問題だけは例外でした。ベルヌーイ数に関する問題は、ラブレース夫人の手間を省くために私が引き受けると申し出たのですが、私が解く過程で重大な間違いを犯していたことに気づき、修正を求めて返送されてきました。
—チャールズ・バベッジ、『ある哲学者の生涯からの抜粋』(1864年)
アラン・G・ブロムリーのような歴史家は、バベッジが1837年から1840年の間に作成した数十のサンプルプログラム(すべて説明ノートよりかなり前に作成されたもの)に注目しているが、それらは出版されることはなく、かなり単純だった[ 6 ]。そのため、一般的にはノートGがコンピュータ専用の最初のアルゴリズムであるとみなされ[ 7 ] [ 8 ] [ 9 ] [ 10 ]、ラブレースが最初のコンピュータプログラマーとみなされている[ 11 ] [ 4 ] [ 1 ] [ 12 ]。
注Gで説明されているプログラムは、解析エンジンが構築されなかったため、バベッジやラブレースの生前にはテストされませんでした。現代では、このアルゴリズムは最新のコンピューティング方法を使用してテストされ、除算演算で2つの変数が入れ替わっているためにソフトウェアのバグがあることが明らかになりました。[ 13 ] [ 14 ]

1840年、チャールズ・バベッジはトリノで解析機関に関するセミナーを行うよう招待された[ 15 ]。これは彼が解析機関について行った唯一の公開説明である[ 16 ] 。バベッジの講演中、数学者のルイージ・メナブレアがフランス語で解析機関の説明を書いた[ 15 ] 。バベッジの友人であるチャールズ・ホイートストンは、貢献するためにラブレースがメナブレアの説明を翻訳すべきだと提案した[ 15 ] [ 17 ]。バベッジは、説明に付録を追加することを提案し、ラブレースはそれを翻訳の最後にAGとラベル付けされた7つの「注釈」としてまとめた。彼女の翻訳は1843年8月にテイラーの科学回想録に掲載され[ 15 ] [ 17 ] [ 18 ]、ラブレースの名前は「AAL」と署名されていた。[ 15 ] [ b ]これらのメモの中で、ラブレースはバベッジの解析機関が計算に使用される場合の能力について説明し、バベッジ自身よりも野心的な計画を提示した。[ 9 ] [ 18 ] [ 19 ]
ラブレースが記事のために書いたメモは、記事本文の3倍の長さだった。[ 20 ]最初のメモでは、バベッジが機械に抱いていた数値的な野望を超えて、機械が計算を利用して音楽、グラフィックス、 [ 21 ]および言語の領域を扱うことができると示唆している。[ 12 ] [ 22 ] [ 23 ]
また、もしその相互の基本的な関係が演算の抽象科学によって表現でき、かつエンジンの操作記譜法と機構の作用に適合させることができる対象が見つかれば、それは数以外のものにも作用する可能性がある。例えば、和声学や作曲学における音高の基本的な関係がそのような表現と適合が可能だと仮定すれば、エンジンはあらゆる複雑さや規模の精緻で科学的な楽曲を作曲できるかもしれない。
—エイダ・ラブレース、翻訳者エイダ・オーガスタ・ラブレース伯爵夫人による回想録「チャールズ・バベッジが発明した解析機関の概略」に関する注釈、注釈A
彼女は読者に対し、解析機関がバベッジの以前の差分機関[ 24 ]とは別物であることを説明し、その機能をジャカード機[ 25 ]になぞらえ、バイナリパンチカードを使用して機械語を表していると述べています。注Cでは、この点は、機械が同時かつ反復的な動作を実行できるため、単一の問題の解決において任意のカードまたはカードの集合を複数回使用できるという事実によってさらに強調されており[ 23 ] 、本質的には現代の制御フローとループの方法を先取りしています[ 20 ] [ 26 ] 。これらのアイデアは、ラブレースが計算の例を示すことを試みた最後の注Gで頂点に達しました。
注Gは、加算、減算、乗算、除算の4つの算術演算のみを使用し、バベッジの構想を実現した。
ここでその目的達成の過程を説明することは不可能であるため、ここでは、算術の最初の4つの演算、すなわち加算、減算、乗算、除算は、機械の介入によって直接実行できると認めるにとどめなければならない。このことが認められれば、機械はあらゆる種類の数値計算を実行できることになる。なぜなら、そのような計算はすべて、最終的に先ほど挙げた4つの演算に帰着するからである。
—チャールズ・バベッジ著「チャールズ・バベッジが発明した解析機関の概略」
また、バベッジのディスク列に情報を保存するというアイデアも使用しており、各ディスク列は次のように表される。(変数の場合)と、参照している列を示す添え字番号。
このアルゴリズムは、ベルヌーイ数を計算するために再帰方程式を使用し、 [ 15 ]方程式内の前の値を使用して次の値を生成します。この方法は次のように実行されます。[ 27 ]
どこは二項係数です。
ベルヌーイ数は様々な方法で計算できますが、著者はエンジンの威力を示すために意図的に複雑な方法を選択しました。ノートGで、ラブレースは次のように述べています。「本稿では、エンジンがベルヌーイ数を計算できる手順を詳細に追跡することで、これらのノートを締めくくります。これは(これから説明する形では)エンジンの威力を示すかなり複雑な例です。」[ 23 ]ノートGで使用されている特定のアルゴリズムは、8番目のベルヌーイ数(次のようにラベル付けされています)を生成します。最初は.) [ 27 ]
アルゴリズムの表は、各コマンドを順番に整理しています。各コマンドは、2 つの項に対して行われる 1 つの操作を表します。2 番目の列には、使用される演算子のみが記載されています。変数は「」と表記されます。「、[ c ]ここで、その前の上付き文字は変数に割り当てられた異なる値の数を表し、その後の下付き文字は変数の順序割り当て、つまりどの変数であるかを表します。(例:は、変数番号4の2回目の割り当てを指します。これまで定義されていない変数には、上付き文字0が付いています。)変数は、から番号が付けられます。3 列目には、実行されているコマンドが正確にコンピュータに伝えられます (たとえば、1 行目で実行されるコマンドは "「 - 変数 2 の最初の反復は、変数 3 の最初の反復で乗算されます。」)であり、1 行につき 2 つの項間の演算は 1 つだけ含まれています。列 4 - 「結果を受け取る変数」は、列 3 の演算の結果をどこに格納するかを記録します。このようにして、この列のすべての変数の上付き番号は毎回 1 つずつ増加します。(たとえば、行 1 では、結果は変数に割り当てられます、、 そして)
5列目には、コマンドの操作で使用された変数のいずれかが変更されたかどうかを示します。中括弧で囲まれたコマンドごとに2行あり、等号の左側に元の変数、右側に新しい変数が配置されます。つまり、変数が変更された場合は上付き文字が1つ増え、変更されていない場合は同じままです。(例:3行目は、次の結果を代入します。)変数の2回目の反復へ、そして5列目には、次のように記されている。
変わったが、そうではない。
6列目の「結果の記述」では、4列目の変数に割り当てられた結果が、以前に割り当てられた2つの項の値に基づいて正確な値で表示されます。(例:1行目 --最初は、 そして変数として設定されました。 したがって、(数式表記で。)この列はエンジンによって計算されるものではなく、プログラムの手順を読者が理解しやすくするためのものと思われます。(例えば、5行目では分数が2で割られていますが、これはおそらく一貫性を保つため、また入れ子になった分数の表記上の複雑さを避けるために、半分を掛けるという表記になっています。)また、プログラムの外部で別の変数表記も使用しています。そして最終値を求めるために順次乗算される変数、したがって:[ 13 ]
さらに、各列には、特定の変数の時間の経過に伴う値が表示されます。変数が変化するか、現在のコマンドの用語の1つとして存在することによってその値が重要になるたびに、その値はそれぞれの列に表示または再表示されます。そうでない場合は、無関係であることを示すために省略記号が付けられます。これはおそらく、コンピュータが関連情報のみを必要とすることを模倣しており、プログラムが解析するにつれて変数の値を追跡します。[ 13 ]
このプログラムは、現代の慣習で第 8 次ベルヌーイ数として知られるものを計算しようとしたもので、以下のように記載されています。ラブレースが数え始めると[ 27 ]
作戦4では、分割が行われているとされているのは「変数に格納されますしかし、「業績報告書」には、分割は次のようになるべきだと記載されている。
実際には、その区分は逆になっている。は、操作2で確認できるように、同様に、は、操作3で確認できるように、操作4は行わない方が良い。むしろこのバグは、エンジンがこの状態でこのアルゴリズムを実行すると、ベルヌーイ数を正しく生成できず、最終目標値(8 番目のベルヌーイ数、)である。
ラブレースのプログラムは現代のプログラミング言語で実装できますが、上記のエラーのため、正確に書き写すと、誤った最終値が返されます。元のプログラムを擬似コードで一般化すると次のようになる。
V[1] = 1 V[2] = 2 V[3] = n /* ラブレースのプログラムでは n = 4 です。 */ /* 始める */ V[4]、V[5]、V[6] = V[2] * V[3] V[4] = V[4] - V[1] V[5] = V[5] + V[1] V[11] = V[5] / V[4] V[11] = V[11] / V[2] V[13] = V[13] - V[11] /* 変数は初期値でゼロです。下記参照。 */ V[10] = V[3] - V[1] V[7] = V[2] + V[7] V[11] = V[6] / V[7] V[12] = V[21] * V[11] V[13] = V[12] + V[13] V[10] = V[10] - V[1] V[10] > 0 の間: V[6] = V[6] - V[1] V[7] = V[1] + V[7] V[8] = V[6] / V[7] V[11] = V[8] * V[11] V[6] = V[6] - V[1] V[7] = V[1] + V[7] V[9] = V[6] / V[7] V[11] = V[9] / V[11] V[12] = V[22] * V[11] V[13] = V[12] + V[13] V[10] = V[10] - V[1] V[24] = V[13] + V[24] V[3] = V[1] + V[3]
擬似コードによる実装は、コンピュータ言語がスタック上に変数を定義するという事実を強調しており、これにより変数の現在の反復を追跡および指定する必要がなくなります。さらに、ラブレースのプログラムでは、以前に定義された変数である 2 つの項に対して加算、減算、乗算、または除算を実行することによってのみ変数を定義することができました。現代の構文では、各計算をより簡潔に実行できます。この制限は、演算 6 (ここでラブレースは、これまで定義されていなかった変数() それ自体で、未定義の変数はすべて自動的に 0 に等しいと想定しているが、ほとんどの現代のプログラミング言語ではエラーが返される。彼女が意図したのは「「」だが、変数のみを項として使用することに限定していた。同様に、演算 8 () 2項算術の厳密な表記法は、定義するために煩雑になる。2 の場合、ラブレースは自身の値 (0) にそれを加える(2)この制限的な表記法により、は次のように定義される。