Skip to content

Instantly share code, notes, and snippets.

@euske
Last active May 13, 2023 14:47
Show Gist options
  • Save euske/955e43554a2c05841eed999adf467ccb to your computer and use it in GitHub Desktop.
Save euske/955e43554a2c05841eed999adf467ccb to your computer and use it in GitHub Desktop.
あるたとえ話 (A parable) - ダイクストラによる、プログラマの魂をもった技師の話。

あるたとえ話 (A parable)

https://www.cs.utexas.edu/~EWD/transcriptions/EWD05xx/EWD594.html

-- エドガー W. ダイクストラ (Edsger W. Dijkstra)

その昔、鉄道会社がありました。その (おそらくはやり手の) 経営者は、 トイレをすべての客車につけず、50% の客車にだけつけるようにすれば、会社の 初期投資をずっと少なくできることに気づき、そのように指示しました。

ところが操業を開始してほどなく、乗客からトイレに関する苦情が続出しました。 調査してみると、経営者の決定がきちんと操車場に伝わっていなかったため、 すべての客車が同じ扱いをされてしまっていました。 創立後まもないこの会社は、すでに情報伝達の問題を抱えていたのです。 結果として、いくつかの列車はトイレがほとんど付かずに走っていました。

[_____] [_____] [_____] [_____] [_____] [____T] [_____] [_____]

この問題を解決するため、トイレつきとそうでない客車を区別し、 すべての列車は2種類の客車を同数使うべしという指示が伝えられました。 操車場の技師たちにとってこれは大変な作業でしたが、 彼らはなんとかそれを達成し、そのことを誇らしく思っていました。

しかし、この新しい方法をもってしてもトイレの苦情は減りませんでした。 さらなる調査をしてみると、たとえトイレつき客車の数が十分でも、 列車によってはトイレつき客車ばかりが一方に固まってしまっている ことがわかりました。

[_____] [_____] [_____] [_____] [____T] [____T] [____T] [____T]

これを解決するために、 「トイレつき客車とトイレなし客車はかならず交互に連結すべし」という 新しい指示が出されました。操車技師たちにとって、これはさらに 困難でしたが、彼らはなんとかやりおおせました。

それでもまだ苦情が来ていました。その理由はこうです。トイレは客車の 端についていたため、客車の向きが悪いと、トイレ間の距離はほぼ 3車両ぶんに なってしまうのでした。さしせまった用がある子供をもつ母親にとっては、 (通路に積まれた荷物のせいもあり) これでも惨事になり得ました。

[_____] [____T] [_____] [T____] [_____] [____T] [_____] [____T]

この結果、トイレつき客車は向きを考慮して、すべてトイレが 同じ向きについていなければならないという指示が下されました。 操車場で使えるターンテーブルの数は限られていたため、 技師たちはこの指示を聞いて喜ぶことはありませんでした。 実際、ターンテーブルの数はまったく足りていなかったのです。 それでも彼らの驚くべき創意工夫によって、なんとかそれが達成できました。

このようにトイレを等間隔につければ、もう問題はないだろうと みんなは考えました。しかしそれでも苦情は来たのです -- (緊急の) 乗客はたとえトイレが近くにあるとわかっていても、 どちらの方向に進めばトイレにたどり着けるかわからないというのでした。

[_____] [____T] [_____] [____T] [_____] [____T] [_____] [____T]

これを解決するため「トイレはこちら→」という表示が トイレなし客車にもつけられることになり、結果として すべての客車の向きを考慮しなければならなくなりました。

この指示が操車場に伝えられると、技師たちは絶望と嫌悪に襲われました。 そんなことはできっこない! しかしこの切迫した瞬間、 ある技師 -- 誰だかもう誰も思い出せないし、追求すべきでもない人物 -- がひとつの事実に気づきました。トイレつき客車とトイレなし客車を ひとまとめで扱うことにすれば、これらの組は実用上、 前後対称として扱ってもよいことになります。つまり、 今後の操車場では向きのある N台の客車を連結するのではなく、 向きのない N/2 組のユニットを連結するようにすればよいのです。

[____T][_____] [_____][T____] [_____][T____] [____T][_____]

この方法は操車場の問題をほぼ一気に解決しました。ささいな問題として、 客車の数はつねに偶数である必要があるのと、この方法では各トイレの間隔が 厳密に等間隔ではなくなります。しかし、わずか3フィートほどの差を 気にする人は誰もいません。

以上は、まだ人類が自動計算機の恩恵を受ける前の時代の物語です。 しかしこの方法を見つけた名もなき技師は、間違いなく世界初の 有能なプログラマと呼ばれるべき人間でありましょう。


私は異なる人々にこの話をしてきましたが、プログラマは一様にこの話を聞くと 歓喜するのに対して、経営者は目に見えて不機嫌になりました。 いっぽう純粋な数学者は、なにが面白いのか理解できないようでした。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment