過去・現在・未来

【 アルゴリズムの標準モデル 】 分散・並列アルゴリズムに、「時間」の概念が必要であることは、ある意味わかりやすいことかもしれない。 計算アルゴリズムの標準的なモデルは、Turing マシンである。多くの人は、分散・並列アルゴリズムのモデルには、Turingマシンは使えないと感じると思う。確かに、Turingマシンには「時間」の概念はない。また、ローカルな「プロセス」という概念もない。そこでの「状態」の概念は、Turing マシン全体にとってグローバルなものだ。 ただ、そうではないと、ランポートは言う。 なぜなら、グローバルなシステムのある不変量という概念は、意味のある概念である。それは、すべての可能なグローバルな状態についての述語であり、特定のグローバルな状態には依存しない。分散システムを実装すると言う問題は、異なるプロセスを通じて、システム全体の不変量を維持することと見ることができる。 ランポートは、並列・分散システムも Turing マシンの標準モデルで記述できると言う。 それでは、前回見たような分散・並列アルゴリズムの記述に必要な「時間」概念は、どうなってしまうのだろうか？　今回 紹介した論文 " The temporal logic of actions "は、まさに、こうした疑問に応えるものだ。 分散・並列アルゴリズムで、ある状態 s が状態 t に変化したとする。これを、s -> t と表すことにしよう。状態 s で利用されている変数を x, y, z, ... とした時、状態 s から変化した状態 t で利用される変数を、状態 s で利用されている変数名にプライム（ダッシュ）を付けて、x', y', z', ... と表すことにする。ここで、状態というのは、変数への値の割り当てであることに留意しよう。 この時、プライムなしの変数とプライム付きの変数から構成される式を、状態の変化 s -> t の「アクション」と呼ぶ。次の式は、アクションの例である。 　　x' = x + 1 この式は、x  の値は、s -> t である状態 t では、状態 s での変数の値 xを使えば、x + 1に変わることを表している。（ s -> t  で変数xの値は、1 増えるということである。） 逆に

【  相対論とプログラミング 】 今回のセッションでは、ランポートの「分散システムにおける時間と時計とイベントの順序付け」という論文を紹介します。 プログラミングをしている時に、アインシュタインの相対性理論を意識している人は、ほとんど絶無だと思います。 ただこの論文は、並列・分散アルゴリズムを理解する上で、相対論的な時間概念が本質的に重要であることを示したものです。（重力理論としての一般相対性理論ではなく、特殊相対性理論の方です。） もっとも、ランポートは相対論を直接に、並列・分散アルゴリズムに応用しようとしたわけではありませんし、この論文を相対論の解説として書いているわけでもありません。 彼は、並列・分散アルゴリズムの「同期」の問題を考えることを通じて、独自に相対論的時間概念にたどり着いているのです。これは、とても興味深いことです。（もちろん、彼は、相対論をよく知っていたと思います。） 彼は、現実の時間を示すリアルな「物理的な時計」に変えて、複数のプロセス上で定義される「論理的な時計」を考えます。この時計は、イベントが起きた絶対的な時間ではなく、二つのイベントで「どちらのイベントが先に起きるか」という相対的な順序関係のみを示します。この「論理的な時計」では、ある場合には、二つのイベントの時間は比較ができない場合もあります。 「我々は、まず最初には、空間的に分離したコンピュータたちのシステムに関心を持つだろう。しかし、我々の見解の多くは、もっと一般的なものに適用可能である。 特に、単一プロセッサーのマルチ・プロセスのシステムは、これらの分散システムと同様の問題を抱えている。なぜなら、起こりうるイベントは予測できない順序で生起するからである。 分散システムでは、時には、二つのイベントのどちらかが先に起きるかをいうことが不可能となる。「先に起きる」という関係が、それゆえ唯一のシステムのイベントの半順序関係である。」 これは並列・分散アルゴリズムについて、本質的に重要な洞察だと思います。 先に、「プログラミングをしている時に、アインシュタインの相対性理論を意識している人は、ほとんど絶無」だと書きました。 ただ、これは本当は、いいことではないように思います。 少なくとも、分散・並列アルゴリズムでは、ミンコフスキーやアインシュタインらの相対論的時間概念に匹敵する、時には常識

【 アルゴリズムの振る舞いを図解する 】 今回のセッションでは、Producer-Consumer同期のアルゴリズムの振る舞いを図解してみようと思います。（アルゴリズムの記述をみて、その振る舞いがわかった方は、読みとばしてもらって構いません。） ポイントは、ProducerのプロセスにもConsumerのプロセスにも登場するawait 命令です。正確にいうとawait の後ろの条件文が重要です。 await 条件文 命令は、条件文が真になるまで、次のブロックの実行をせずに待機し続けます。逆にいうと、条件文が偽になった時初めて、次のブロックを実行します。 Producerのawait 命令は、await Len(buf) < N という形をしています。Consumer のawait 命令は、await Len(buf) > 0　という形をしています。どちらの条件文にも、 使われているバッファーの長さを示す Len(buf) という式が含まれています。 このことは、ProducerのプロセスとConsumerのプロセスの同期に、この式の値が利用されていることを示しています。以下では、LB = Len(buf) と表すことにしましょう。 LB = N となるのは、どういう場合でしょうか？　それは N個の容量を持つバッファーが全て使われている場合です。この時、バッファーにはデータを受け入れる余裕がないので、データを入力 in からバッファー buf に送り込もうとするProducer は待機を続けます。 LB = 0 となるのは、どういう場合でしょうか？　それは バッファーが空の場合です。この時、バッファーには読みこむべきデータがないので、データをバッファー buf から読み込んで出力 out に送り込もうとする Consumer は待機を続けます。 結局、ProducerとConsumerの待機状態が解けて、それぞれのプロセスが本来の仕事をするのは、 0 < NB < N の場合だけであることがわかります。ProducerはNBの値を一つだけ増やし、ConsumerはNBの値を一つだけ減らします。 一つ注意したいことがあります。 以前に、「振る舞いは、状態の変化の系列だ」と述べたと思います。ただ、Produucer, Consumer プロセスが待

【 アルゴリズムの不変量 】 並列アルゴリズムを、状態の遷移として記述するアプローチを「状態モデル」と呼びます。 このアプローチとは別に、イベントの継起として並列アルゴリズムを記述するモデル「イベント・モデル」があるのですが、それについては後で述べます。 状態モデルでは、 　● 状態は、変数への値の割り当てです。 　● 状態の遷移の系列を「振る舞い Behavior」と呼びます。 　● 状態の遷移を引き起こすものを「アクション」と呼びます。 同一のFIFOアルゴリズムでも、可能なシステムの振る舞いは、多様です。それは無数に存在します。 ここでは状態の遷移を引き起こすアクションを並べて、振る舞いを記述してみます。先のセッションを参照ください。 システムの可能な振る舞いの例 1 　　P P P C P C P … システムの可能な振る舞いの例 2 　　P C P C P C … システムの可能な振る舞いの例 3 　　P P P C C C P … このアルゴリズムに基づく振る舞いは無限個存在するのですが、重要なことは、この状態モデルで全てのアクションの実行の全てのステップで成り立つ、状態についての論理式が存在刷ることです。 こうした状態についての論理式を、アルゴリズムの「不変式」「不変量」と呼びます。 次に見るbounded FIFO queue のアルゴリズムの「不変量」の存在は、このアルゴリズムがN個の容量のバッファを持つbounded FIFO queue の正しい仕様であることを示唆しています。 N個の容量のバッファを持つ bounded FIFO queueアルゴリズムの「不変量」は次のものです。 　　( Len(buf) ≦ N ) ∧ ( Input = out◦buf◦in ) ここで、記号◦は、リストの結合を表しています。 最初の項( Len(buf) ≦ N ) が成り立つのは、バッファーの容量は、高々N個であるという仮定から明らかです。 第二項 ( Input = out◦buf◦in ) については、初期状態では、Input=in で out=buf=<.> で成り立っています。 ある状態 st でこの式が成り立っていると仮定して、その次の状態 st’ でもこの式が成り立っていることを示せば、帰納法でこの式が不変量であることを示すこと

【 アルゴリズムとプログラムは違うものです 】 プログラムとアルゴリズムは似ています。 我々は、歴史的には、アルゴリズムの記述に、疑似的にプログラム言語を利用してきました。 だから、同じアルゴリズムの説明に、異なるプログラム言語が利用されていても -- 例えば、ある場合にはALGOLが、ある場合にはCが利用されていても --大きな違和感を感じることはなかったかもしれません。 なぜ、複数の異なるプログラム言語が、同一のアルゴリズムの記述に利用できるのでしょう？ それは、自然言語では普通のことです。同じ意味を、大抵の場合、日本語でも英語でもフランス語でも、異なる言語で表現できるからです。 プログラムとアルゴリズムは異なるものです。 プログラムは、具体的なコンピュータによって具体的に実行されるものですが、アルゴリズムは、その「具体的実行」の背後に存在する抽象的な「意味」に関わるものです。 そうしたプログラムの「意味」の記述としてのアルゴリズムの記述は、プログラム言語とは異なる形式が必要です。 ある意味当然のことですが、プログラムとアルゴリズムの違いの認識が生まれたことは重要なことです。さらには、一歩進んで、アルゴリズムを記述する言語の必要性の認識が生まれたことは、とても重要なことです。 ただし、残念なことは、こうした認識は、必ずしも多くの人に共有されていないと思います。 視点を変えましょう。 アルゴリズムとプログラムとの関係は、実践的には、「仕様」とその実装としての「プログラム」の関係としても考えることができます。 アルゴリズムの記述が「仕様」として与えられ、その実装が「プログラム」として与えられるということです。 ランポートによってアルゴリズム記述言語で与えられた、先に見た Algorithm PC は「仕様」です。bounded FIFO queueのプログラムは、この仕様としてのアルゴリズムを実装しなければなりません。 仕様は定義です。ある定義が正しいかと問うことは、形式的には意味がありません。 しかしながら、このアルゴリズムのいくつかの性質を証明することによって、我々はこのアルゴリズムがまさにbounded FIFO queueの仕様であることに確信を持つことができるのです。 我々があるアルゴリズムについて証明する最も重要な性質は、「

【 花咲く季節 】 今年は、サロベツも西海岸もエゾカンゾウ、当たり年でした。 去年は、サロベツの花は、この様子じゃいつか見られなくなるかもと落胆していたのですが。 サロベツだけじゃないんです。今年は、空き地にも道ばたにも、タンポポ、エゾタンポポ、マーガレットが沢山花を咲かせています。 昨日は、メグマ沼にアヤメの群生を、バッカイ（抜海）にスイレンを見に行きました。どちらの花も見事でした。そういえば、宗谷のクロユリの群生、見逃したこと残念です。これらの花、これまで僕は一度も見に行ったことなかったのですが。 鳥も鳴かず花も咲かない「沈黙の春」的な予想がはずれて、この「騒々しい未来」がおとずれたこと、嬉しいと思います。 今年は、花にとって、まるで、思いがけない何かが起きたようです。 最北の二つの島、利尻島と礼文島では、今年、全島でササの花が咲きました。120年に一度の出来事だと言われているようです。花を咲かせた後、ササは枯れて、その一生をおえるのだそうです。 今年の宗谷の花の大饗宴は、吉なのでしょうか？　それとも凶なのでしょうか？

【 なぜ、歴史を振り返るのか？ 】 このセミナーでは、一方では、ダイクストラらが登場し活躍した、ほぼ60年ぐらい昔の話を紹介しています。同時に、ランポートのTuring賞受賞記念講演をベースに、21世紀の視点から、並列アルゴリズムの "Early Days" を振り返ろうとしています。 なぜ、過去を振り返るのでしょう？ それには、意味があるのでしょうか？ 　 少なくともコンピュータのハードウェアに関しては、その過去を振り返ることは、技術史的興味や懐古趣味を別にすれば、あまり意味のあることのようには思えません。多分、60年前のコンピュータのハードウェアから、学べることは少ないと思います。 ただ、ハードウェアの進化・発展のまばゆい後光の奥には暗闇があります。 そこに目を凝らせば、別の様相が見えてきます。 一つには、並列・分散の「古典的」アルゴリズムは、この数十年大きな変化はないまま、多くの人に受け入れているように見えます。ただ、重要なことは、そのことは、こうしたアルゴリズムが「正しい」ものとしてしっかりと基礎付けられていることを意味しません。 もう一つには、もちろん、並列・分散のアルゴリズムを基礎づけようとする着実な試みが、存在することです。残念ながら、こうした取り組みの成果は、多くの人には届いていないように見えます。 こうした認識は「アカデミック」で「実践的」ではないと感じる人も多いでしょう。 でも、それは違うと僕は考えています。 何よりも、現代のコンピュータ・サイエンスを支えてきた最大のバックボーンである現実の世界でのコンピュータ技術の爆発的発展・普及が、新しい理論的枠組みを要求していると考えているからです。 高速化・高密度化するハードウェアのもとで、光の信号でさえ、ワン・クロックでも基板上数十センチしか進みません。こういう時、我々は「同期」の基礎である「同時性」をどのように考えればいいのでしょう？ 量子コンピュータのもとでの情報の「不確実性」だけではなく、量子エンタングルメントでの一見すると時空にとらわれない「因果関係」の登場、こうした問題は、情報処理技術の未来に深く結びついています。 あまり、顧みられていない探求の歴史から、学ぶことは多いと考えています。　 -------------------------------------------

【 すみっこぐらし 】 稚内でも暑い日が始まりました。 今年初めてエアコンのスイッチを入れたのですが、うんともすんとも反応しません。 故障発覚から二日後の昨日の朝、ダイキンさんが、エアコン修理に来てくれました。 というか、コンセントをチェックしていたのですが、 　「あれ、これ電気きてないですね。」 電気がなければエアコン動かないですね。ただ、本体故障以外の電源工事や設置工事の問題は、別業者の責任区分になるとのこと。確かに、電気が来てなくて動かないエアコンは故障とは言えないし、修理のしようもないですからね。 どうすればいいの？　たらい回しになるのを一瞬心配したのですが、ダイキンさん、設置業者のケーズ電気さんに直接連絡をとって、事情を説明しくれました。 夕方、今度は、ケーズ電気の人が来てくれて配電盤をチェック。 　「あれ、これ、ここまで電気きてないですね。」 3年前、エアコンを買い替えた時、少し大型のにしたのですが、その時エアコン用に200Vの電源を用意してもらいました。100Vの方はちゃんと電気が来ているんですが、200Vの方の電気が来ていないとのこと。 屋内の配電工事はケーズさんの責任区分だけど、200Vの配電は北電さんの責任区分だといいます。デジャヴュです。 ただ、いいデジャヴュもあるんですね。今度も、ケーズさんが直接北電さんに連絡をとってくれ、夜の9時近くになって、今度は北電さんが来てくれました。 　「やはり、200V きてないですね。」 そんな。去年の夏はちゃんと動いていたのに。 ただ、さすがプロですね。思い当たることがあるようで、暗い戸外に出ていきました。家のブレーカーも落として欲しいというので、僕らも電気のない暗い室内で待機です。 10分もしないで戻ってきて、 　「ブレーカー入れて、エアコン試してもらえますか？」 なんと、エアコン復活しました。よかった。 北電さん、 　「こちらの施工不良です。」 と、いさぎよく、非を認めました。えらい。 ダイキン、ケーズ、北電の伝言ゲームは、一日で首尾よく終了です。 でも不思議です。どうして、それまで問題なかった戸外の配電にトラブルが起きたのか。 一つだけ思い当たることがあります。家の近くの電柱が、冬の間に除雪車にぶつかって傾いていたので、先週、大規模な修理工事をしていました。あるいは、その工事に關係あるのかもしれません。

【 次章へ。その前に ... 】 今回から、「生産者消費者同期」の話題に入ろうと思います。 「生産者消費者同期」問題というのは、データを生み出すデバイス（生産者）とデータを受け取るデバイス（消費者）との間をどう同期させるのがいいのかという問題です。 コンピュータが誕生したその最初期から、ハードウェア的な「バッファー」は使われてきました。バッファーのコントロールは、典型的な「生産者消費者同期」問題です。    その前に、というか、その最初に、ダイクストラの  semaphore を取り上げようと思います。というのも、この問題を初めて並列プログラミングの問題として捉え、semaphoreを利用してこの問題を定式化したのは、ダイクストラだったからです。 semaphoreの性質をまとめておきましょう。 　● semaphore というのは、全てのプロセスから共通にアクセスできる、0 または 正の整数値を取る変数のことです。 　● semaphore には、値を +1だけ増やす操作と、値を -1だけ減らす操作が用意されています。 　● semaphoreに対する操作は、アトミックに行われます。（他のプロセスが操作途中に介在することを許さない） これだけですが、semaphoreの導入は、並列アルゴリズムの記述に、大きな威力を発揮します。 今回のセッションでは、以前見たダイクストラの 「排他制御アルゴリズム」と、これから見ていく「生産者消費者同期アルゴリズム」が、semaphore を使うとどう記述できるかを紹介したいと思います。　 ------------------------------------------- セッションの動画のURL https://youtu.be/KFOxAummbBg?list=PLQIrJ0f9gMcOeqlB09PdBddfXLv2QjG-F スライドのpdf https://drive.google.com/file/d/13xbaDAWvH0ETk-KZFHEYzVViM32TJYjz/view?usp=sharing 関連blog 「次章へ。その前に ...」 https://maruyama097.blogspot.com/2022/07/blog-post_15.html 参考資料 Dijkstra, E.W. Cooperat

【 無理は承知で ... 】 このセッションでは、ランポートの「パン屋のアルゴリズム」の新しいバージョンを紹介します。 何が新しいかというと、彼はアルゴリズムを記述するのに「並列にプロセスを実行する」という命令を導入して、その命令を使って「パン屋のアルゴリズム」を書き換えました。 以前のアルゴリズムそのものにに不満があったというより、そのアルゴリズムの「正しさの証明」 -- Assertiion ベースの証明に不満があったようです。 アルゴリズムの新しい記述法の導入にともなって、「並列にプロセスを実行する」とはどういうことなのか、「プロセスの相互排除」とはどういうことなのかを、改めて考えることになりました。 彼が注目したのは、時間の問題です。プロセスAの実行時間とプロセスBの実行時間の、時間軸上での関係を考えます。 プロセスAの実行が完全に終わってからプロセスBの実行がはじまる、あるいは、その逆に、プロセスBの実行が完全に終わってからプロセスAの実行がはじまるなら、それは、プロセスAとプロセスBの「並列実行」とは言いません。 並列実行（コンカレントな）実行というのは、二つ以上のプロセスが同時あるいは時間的には重複して実行される状態をさします。 critical section にはたかだか一つのプロセスの侵入しか許さないという、プロセスの相互排除が目指している状態は、それとは、まったく逆のものです。 プロセスAの実行が完全に終わってからプロセスBの実行がはじまる、あるいは、プロセスBの実行が完全に終わってからプロセスAの実行がはじまること、それが、プロセスAとプロセスBの相互排除です。 時間の流れが、過去から未来に一方向に流れている様に見えるのですが、世の中には、同時に起きることはたくさんあります。継起するイベントと同時に起きるイベントの数を比較してみてもいいのですが、「同時性」という概念自体、きちんと定義されるわけではありません。 とまれ、同時に走る並行プロセスでプロセスの相互排除を実現しようとすることは、本来同時並行に生起するものを無理やり一列に並ばせるようなものです。もちろん、こうした原理的には困難に思える無理を承知で、可能なアルゴリズムを模索しているのです。 ------------------------------------------- セッションの

 【 「パン屋のアルゴリズム」を図解する 】 このセッションでは、ランポートのアルゴリズムが正しいことを、ランポートの論文に従って示そうと思います。できるだけ図を使おうと思います。 ランポートは、アルゴリズムについての「三つの主張」が正しいことを示すことで、「パン屋のアルゴリズム」の正しさを証明しようとします。 三つの主張で重要なのは、critical section に入れるのは一つのプロセッサーだけだという主張（主張 2）と、レジ待ちのプロセッサーは、いずれ、critical section に入るという主張（主張 3）の二つです。 前者（主張 2）は、排他制御の safety という性質で、後者（主張 3）は、排他制御の liveness という性質です。ただし、この論文では、ランポートは、こうした言葉を使っていません。 アルゴリズム自身が進化・発展するだけでなく。アルゴリズムの記述のスタイル、アルゴリズムの正しさの証明のスタイルも時代と共に変化していることに留意してください。 このセッションで見るアルゴリズムの正しさの証明は、チケット番号全体に対する読み書きが、アトミックに行われる必要はないことを示しています。このbakeryアルゴリズムは、その値がコンカレントに書き込まれたものでないとしても、その読み出しが正しい値を返すならば、正しいのである。書き込みと重なった読み出しがどんな値を返すかは問題ではないのです。 コンカレントな書き込みによって9から10に変わろうとしているある数の読み出しが、2496という値を返したとしても、このアルゴリズムは正しいのです。 bakeryアルゴリズムの、この驚くべき性質は、それがプロセスがチケット番号に相互排除的にアクセスすることを想定していない相互排除のアルゴリズムの実装であることを意味しています。それは、下位のレベルの相互排除を前提としない、相互排除アルゴリズムの最初の実装です。　 1973年当時は、そうしたことは不可能だと考えられていました。1990年になっても、専門家でさえ、それは不可能だと考えていたように見えます。 ------------------------------------------- セッションの動画のURL https://youtu.be/0YdFQGPkyHE?list=PLQIrJ0f9gM

【 これは、やさしいアルゴリズムだ！】 今回は、排他制御のアルゴリズムとして、ランポートの「bakery アルゴリズム」というのを紹介しようと思います。 「bakeryアルゴリズム」は、「パン屋のアルゴリズム」ということです。混雑している人気のパン屋をイメージしましょう。こんな感じです。 ● パン屋の店先には、番号付きの整理券を発行する機械がある。整理券の番号は一つづつ増えていく。 ● お客は、パン屋に入る前に、機械から整理券を受け取る。同時に一人しか整理券を受け取れない。 ● パン屋には、一つのレジしかない。一番小さな番号の整理券を持ったお客から、パンを買うことができる。 パン屋じゃなくても病院でも銀行でも、身の回りの日常で混雑整理の方法として、よくみる風景ですね。 最初に、先行したダイクストラらのアルゴリズムの特徴をおさらいしておきましょう。それは、次のような性質を持っていました。 ● どの時点でも、多くても一つのコンピュータしかcritical sectionに入ることができない。● どのコンピュータも、（途中でマシンが停止しなければ）最終的にはいずれcritical sectionに入ることができる。 ● どのコンピュータも、非critical sectionで停止しても構わない。また、それぞれのコンピュータの処理スピードは問わない。 ランポートのアルゴリズムでは、最後の実際にレジでパンを買うところが、critical sectionに入ることに相当します。ダイクストラらの排他制御アルゴリズムの特徴を、ランポートのbakery アルゴリズムが持つことは、直感的には明らかに思えます。 だって、 　レジでパンを買えるのは、一人だけ。 　整理券を持っていれば、いずれ、パンを買える。 　途中で店を抜けても、時間をかけてゆっくりパンを選んでも構わない。 ですからね。 その上、アルゴリズムはとてもわかりやすいですね。ソースにコメントを入れました。ダイクストラのアルゴリズムでギブアップした人も、ランポートのアルゴリズムのわかりやすさを体験ください。 ただ、アルゴリズムのわかりやすさだけが、ランポートのアルゴリズムのメリットではないのです。実は、ダイクストラらのアルゴリズムには（クヌース、ド・ブルイジンらの「改良版」でも共通に）、実践的には弱点がありました。 それは、N台の

【 あのころみんな若かった 】 ダイクストラは、読者に論文を最後まで読む前に、しばしたちどまって、自分自身で問題を考えてほしいと、問題への挑戦を呼びかけています。 「というのも、そうすることが、それぞれのコンピュータは、同時には一方向のメッセージを要求することしかできないという事実のトリッキーな帰結をしっかりと感じてもらう唯一の方法のように思えるからだ。」 「そして、それのみが、どの程度までこの問題が、トリビアルな問題からは遠い問題であることを、読者に理解させるだろう。」 なかなか挑発的です。ダイクストラは、このアルゴリズムの発見で高揚した気分になっているようにも思えます。今だったら、「論文に、こんなこと書かなくていいから」と指導教員からダメ出しされそうです。 ダイクストラのアルゴリズムというのは、10数行で記述されているとても短いものです。1日、1000行近いコードを生産するプログラマを、僕は何人か知っています。20行足らずのコードなんて、読むのも書くのも簡単だと思われるかもしれません。ただ、そうではありません。 事実、ダイクストラのアルゴリズムは、すぐに多くの人に正確に理解されたわけではないようです。ある日事件が起きます。ダイクストラの論文が掲載されたComm ACM誌の編集部宛に、Hymanという人が、コンピュータが2台の場合、ダイクストラのアルゴリズムをもっと簡単にできるという趣旨の手紙を出し、それが掲載されたのです。ただ、それは、間違ったものでした。 この手紙に最初に反応したのは、クヌースでした。（のちに、ド・ブルイジンも参戦します。） 「Hyman氏の「解法」なるものの反例を見つけるのは簡単である。（氏の12行のプログラムには、ALGOLの文法エラーが15個も含まれているのだが、たとえそれでも、何人かの読者は、彼のプログラムを理解できたかもしれないと、私は信じている。）」 キツイいいかたですね。でも、クヌースのダイクストラのアルゴリズムの理解は正確なものでした。その上、彼は、ダイクストラのアルゴリズムには、いくつか問題があることも指摘しています。さすがクヌース。　 Knuth, Additional Comments on a Problem in Concurrent Programming Control  https://dl.acm.org/do