上級その5

こんにちは!このページは「コンピュータサイエンスと魔法のYコンビネータ」という記事の17ページ目です。1ページ目から読むにはこちらからどうぞ

コンピュータサイエンスと
魔法のYコンビネータ

エピローグ: コンピュータサイエンス

スライド 1 / 15

これが最後のページです!

これが最後のページです。ここまで読んでくださり、ありがとうございました!

お疲れ様でした!

他のページをお探しですか?

上級その5·
スライド 2 / 15

そもそも弁当箱というアイデアはどこから来たのか

さて、前回の最後に、ラムダ村の村人は次のような質問をしました。

弁当箱にできない計算はあるのかな?

この質問に答えるためには、「そもそも弁当箱というアイデアはどこから来たのか」という質問にまず答える必要があります。

そもそも、弁当箱というアイデアは
どこから来たのか?

そのためには、ラムダ村の世界ではなく、現実世界の歴史を学ばないといけません。

現実世界の歴史を学ばないといけない

というわけで、これから現実世界の歴史の話をします。ラムダ村の話からはいったん離れますが、このページの最後で戻ってきます。

ちなみに: これからコンピュータやコンピュータサイエンスの歴史について語りますが、簡潔さを優先するために、正確性をあえて犠牲にしたり、ほとんどの出来事を省いたりしています

コンピュータ史に詳しい方のなかには、怒り心頭に発する方が出てくるかもしれません。雑な歴史の紹介であることをお許しください。

スライド 3 / 15

そもそもコンピュータとは何か

この記事のタイトルは「コンピュータサイエンスと魔法のYコンビネータ」ですが、はじめに、「そもそもコンピュータとは何か」という質問について考えてみましょう。

そもそもコンピュータとは何か?

「コンピュータ」というとパソコンやタブレット、スマホ、ロボットを思い浮かべる方が多いかもしれません。

しかし、コンピュータは本質的には「計算機」なのです。

コンピュータは本質的には「計算機

コンピュータを使えば情報を瞬時に検索できたり、美しいCGを描いたりすることができます。最近はAIを使って顔認証や会話ができるようになりました。

こういった便利な機能は、 コンピュータが大量の計算を瞬時に行えるからこそ実現されているのです。

たとえば、検索エンジンは膨大な数のデータをランク付けするために計算を行います。AIが顔認証をするときは、センサーが取り込んだ顔のデータを数値化し、それをもとに複雑な計算を行って本人かどうかを確かめているのです。

コンピュータは、大量の計算を行える計算機

だから、コンピュータは「計算機」なのですね。

スライド 4 / 15

計算機の歴史

コンピュータは計算機であるからこそ、コンピュータの歴史はすなわち、計算機の歴史なのです。

歴史を振り返ると、たとえば昔の日本では、中国から伝わったそろばん が計算機の主役でしたね。

昔の日本で「計算機」といえば
そろばんだった

一方、海の向こうのアメリカでは、1890年に「タビュレーティングマシン」という計算機が台頭しました。

Hollerith_census_machine_at_the_Computer_History_Museumシリコンバレーのコンピュータ歴史博物館に展示されているタビュレーティングマシン(撮影: Anton Chiang, CC BY 2.0)

タビュレーティングマシンは、アメリカの国勢調査、すなわち国全体のアンケート調査を集計するために使われた計算機でした。マークシートのような紙に空いた穴を読み取って計算することで、大量のデータをすばやく集計できたのです。現代のエクセルのようなものですね。

アメリカでは「タビュレーティングマシン」
という計算機が国勢調査で使われた

ちなみに、この計算機の発明者であるホレリスは、IBMの前身となる会社を創業しました。IBMはさらに強力な計算機を開発し続け、1960年代に世界一のコンピュータ企業になったのです。

スライド 5 / 15

計算機「科学」のはじまり

上記の「タビュレーティングマシン」を皮切りに、計算機は20世紀に入ってどんどん進化していきました。やがて計算機は電子化され、今の「コンピュータ」と呼ばれるような機械になっていきました。

計算機は20世紀にどんどん進化した

いっぽう同時期に、計算機について科学する学問である「コンピュータサイエンス=計算機科学」 も生まれ、進化していきました。

そんなコンピュータサイエンスの研究者たちは、「コンピュータ=計算機の作り方や使い方をどう工夫すれば、より効率的に問題を解けるのか」といった問いに取り組んだのです。

コンピュータサイエンス:
計算機の作り方や使い方をどう工夫
すれば、より効率的に問題を解けるのか

そして、コンピュータサイエンスの礎を築いたと言われているのが、英国の数学者だったアラン・チューリング と、米国の数学者だったアロンゾ・チャーチ です。ふたりの研究が、学問としてのコンピュータサイエンスの大本になっているのです。

アラン・チューリング
アロンゾ・チャーチによる
研究が、コンピュータサイエンスの礎となった
スライド 6 / 15

空想上の計算機

チューリングとチャーチは1930年代に、「ヒルベルトの決定問題」という、とある難しい数学の問題に別々に取り組んでいました。それがどんな問題かを説明するのは非常に難しいので省略しますが、ふたりがその問題をどのようにして解いたかが興味深かったのです。

チューリングチャーチは、
とある数学の問題に別々に取り組んでいた

その問題を解くために、ふたりはそれぞれ別々の「空想上の計算機」を考案する必要がありました。「空想上の計算機」とはすなわち、実際には(少なくとも1930年代の当時は)存在しないけど、もし存在したとしたら非常に複雑な計算ができる、仮想上の計算機のことです。

空想上の計算機とは、
実際には存在しないが、もしも存在したら
非常に複雑な計算ができる
仮想上の計算機のこと。

もし仮にそんな計算機がこの世に存在したら…」と仮定したうえで理論を展開することで、ふたりはそれぞれ別々に、先述の問題を解くことができたのです。

先述の問題を解くために、ふたりはそれぞれ
空想上の計算機」を頭の中で設計した。
もしこういった計算機が存在したら…」と
仮定した上で理論を展開して問題を解いた

実は、この時にふたりが別々に考案した、当時の技術では作ることができない「空想上の計算機」が、その後のコンピュータの開発や、プログラミング言語の開発、ひいてはコンピュータサイエンスそのものに大きな影響を与えました。

言い換えると、このふたりは「ヒルベルトの決定問題」という数学の問題を解いていたのですが、その問題を解くためにふたりが考えたアイデアが偶然にも、近代のコンピュータサイエンスの土台になったのです。


1930年代半ばに、チューリングは先述の問題を解くために「チューリングマシン」という空想上の計算機を考案しました。「このチューリングマシンが仮に存在したら…」と論を展開することで、彼は先述の数学の問題を解くことができたのです。

そして、ここでは詳しく説明しませんが、このチューリングマシンの仕組みはシンプルながら、現代のコンピュータの仕組みと非常に似ており、近代的なコンピュータの発展に大きな影響を与えたのです。

チューリングは、「チューリングマシン
という、現代のコンピュータに似ている
空想上の計算機を頭の中で考え、
それを使って先述の問題を解いた

一方、ほぼ時を同じくして、チャーチは先述の問題を解くために「ラムダ計算」という空想上の計算機を考案しました。では、この「ラムダ計算」とはどんな仕組みだったのでしょうか。

チャーチは、「ラムダ計算」という
空想上の計算機を頭の中で考えた

実は、みなさんはすでに「ラムダ計算」がどんな仕組みかを知っています。そう、 弁当箱のことです。

チャーチが考えた空想上の計算機
ラムダ計算」は、弁当箱と仕組みが同じ
スライド 7 / 15

ラムダ計算と弁当箱

チャーチが考えた空想上の計算機「ラムダ計算」は、見た目は弁当箱とは違いますが、仕組みは同じでした。

ラムダ計算。弁当箱と仕組みは同じ

たとえば、こちらが「ラムダ計算」の記述式です。一番左にある「λ」の記号はギリシャ文字で「ラムダ」と呼ぶことから、「ラムダ計算」と呼ばれています。

λA.B C

上のラムダ計算の記述式は、以下の弁当箱とまったく同じことを表しています。

上のラムダ計算の記述式は、
この弁当箱とまったく同じ
1
1

上の弁当箱は、実行 すると になります。早送り を押してみてください:

1
1

それと同じで、先ほどの「ラムダ計算」の記述式も、実行 するとBが残るのです。

λA.B C
B

もちろん、もっと複雑なラムダ計算の記述式もあります。たとえば、こちらをご覧ください。この記述式は、何を表しているか分かりますか?

λA.(λB.A(B B))(λB.A(B B))

答えを言うと、上の記述式はYコンビネータを表しているのです。つまり、下の弁当箱とまったく同じです。

上のラムダ計算の記述式は、
Yコンビネータ」の弁当箱と同じ
1
12
2
1
1
12
2
1

つまり本稿では、実はみなさんにラムダ計算を教えていたのです。ラムダ計算の記述式は見た目が複雑なので、「弁当箱のパズル という形で教えることで、とっつきやすくしていたというわけですね。

本稿では、実はラムダ計算を教えていた。
ラムダ計算の記述式は見た目が複雑なので、
「弁当箱のパズル という形で教える
ことで、とっつきやすくしていた。

そして繰り返しますが、このラムダ計算は、1930年代に考えられた「空想上の計算機」というわけです。

スライド 8 / 15

村人の質問に戻ると…

ここで、ラムダ村の村人の質問に戻りましょう。

弁当箱にできない計算はあるのかな?

先ほど、「弁当箱とラムダ計算は同じ」という話をしましたね。つまり、上の質問は以下のように言い換えることができます。

ラムダ計算にできない計算はあるのかな?

では、ラムダ計算にできない計算はあるのでしょうか?

結論から言うと、ラムダ計算は、現代のコンピュータが行うことができるすべての計算を行うことができます。つまり、あなたのパソコンやスマホができる計算はすべて、ラムダ計算にもできるということです。

ラムダ計算は、現代のコンピュータが行える
すべての計算を行うことができる

ということはつまり、弁当箱も、現代のコンピュータが行えるすべての計算を行うことができるというわけですね。

弁当箱も、現代のコンピュータが行える
すべての計算を行うことができる

このことは、1930年代に証明されました。「これから先にどれほど強力な計算機が登場しても、その計算機ができる計算は、理論上はラムダ計算にもできる」ということが数学的に証明されたのです。もちろん、この証明は難しすぎるので省略します。

「どれほど強力な計算機が登場しても、
その計算機ができる計算は、
理論上はラムダ計算にもできる」と
1930年代に証明された

ちなみに: チャーチが考案したラムダ計算だけでなく、チューリングが考案した空想上の計算機「チューリングマシン」も、現代のコンピュータが行えるすべての計算を(理論上は)行うことができます。このことも、1930年代に証明されました。

スライド 9 / 15

ラムダ計算の影響

先ほど説明したように、ラムダ計算はもともと、とある数学の問題を解くためにチャーチが考案したものでした。しかし、ラムダ計算もまた、コンピュータサイエンスの発展に大きな影響を与えたのです。

ラムダ計算は、コンピュータサイエンスの
発展に大きな影響を与えた

特に、ラムダ計算は数々のプログラミング言語に影響を与えました。現存するプログラミング言語の多くには、ラムダ計算の名残が残っています。

たとえば、執筆時点で世界で最も人気のプログラミング言語のひとつである、Python (パイソン)という言語があります。ちなみにパイソンとは大蛇のことで、Python言語のロゴにもヘビの絵が描かれています。

Python言語

このPython言語にも、「lambda (ラムダ)」という機能があります。たとえば、以下のPython言語のコードをご覧ください。

(lambda A: A)('B')

上のPython言語のコードは、以下のラムダ計算とほぼ同じ意味です。

λA.A B

これは、弁当箱に例えると以下のようになり、実行結果は になります。

下が左右とも同じなので…
1
1
上にあった が残る

だから同じように、今回紹介したPythonのコードも、実行すると結果は B になります。

(lambda A: A)('B')
'B'

まとめると、Python言語のような人気のプログラミング言語も、1930年代に考えられたラムダ計算の影響を間接的に受けているのです。

Python言語のような
人気のプログラミング言語も、
1930年代に考えられた
ラムダ計算の影響を間接的に受けている
スライド 10 / 15

工夫すること

そろそろ終わりが近づいてきましたが、最後に「コンピュータサイエンス=計算機科学」についてもう一言だけお話をさせてください。

それは、計算機を工夫すること」が、コンピュータサイエンスではとても大事というお話です。

重要: 計算機を工夫することが、
コンピュータサイエンスではとても大事

今回紹介したラムダ計算、すなわち弁当箱は、仕組みはとてもシンプルです。弁当箱の基本の法則は、初級その3〜5で紹介したように、非常にシンプルです。

弁当箱の基本の法則は非常にシンプル

しかし、こんなシンプルな弁当箱でも、現代のコンピュータが行えるすべての計算を行うことができるのです。それができる理由は、弁当箱を工夫すれば、四則演算や、条件分岐や、繰り返しを行うことができるからです。

弁当箱を工夫すれば、四則演算や、
条件分岐や、繰り返しを行うことができる

たとえば今回紹介した通り、Yコンビネータの弁当箱を使えば、繰り返しを行うことができますよね。他にも工夫次第で、さまざまな計算を行うことができます。

Yコンビネータ」の弁当箱を使えば
繰り返しを行うことができる
1
12
2
1
1
12
2
1

コンピュータサイエンスは、「計算機(コンピュータ)の作り方や使い方をどう工夫すれば、より効率的に問題を解けるのか」について考える学問です。

そして、今回学んだ弁当箱は、シンプルでも工夫次第で複雑な計算ができる計算機です。そんな弁当箱には、コンピュータサイエンスのエッセンスが詰まっていると思うのです。

弁当箱は、シンプルでも工夫次第で
複雑な計算ができる計算機。だからこそ
コンピュータサイエンスのエッセンスが
詰まっている
スライド 11 / 15

コンピュータサイエンスの他の分野でも同じ

今回は時間の都合で、たくさんあるコンピュータサイエンスの題材のうち、ラムダ計算(弁当箱)しか紹介できませんでした。

とはいえ、コンピュータサイエンスの他の分野を学ぶときも、やることは弁当箱のときと同じです。なぜならどの分野でも、弁当箱のように「計算機(コンピュータ)を工夫して、問題を解く」ことが大事になってくるからです。

コンピュータサイエンスのどの分野でも、キーワードは「工夫」なのです。たとえば、「コンピュータをどう工夫して使えば、美しいCGや、人工知能や、仮想通貨が作れるだろう?」といった感じですね。

コンピュータをどう工夫して使えば、
美しいCGや、人工知能や、
仮想通貨が作れるだろう?

長くなりましたが、本稿を読んで、「コンピュータサイエンスの他の分野でも、コンピュータの工夫の仕方を学んでみたい」と思ってくだされば嬉しいです。

スライド 12 / 15

まとめ

本稿で学んだことを短くまとめると、以下のようになります。

  1. 弁当箱は、工夫次第で四則演算や、条件分岐や、繰り返しといった複雑な計算ができる。また、繰り返しを行う弁当箱をYコンビネータと呼ぶ。
  2. 弁当箱は、1930年代に考案された空想上の計算機「ラムダ計算」が基になっている。ラムダ計算は、現代のコンピュータが行えるすべての計算を行うことができ、また多くのプログラミング言語に影響を与えた。
  3. コンピュータサイエンスは「計算機(コンピュータ)をどう工夫して問題を解くか」を考える学問。工夫次第で複雑な計算ができる弁当箱には、そのエッセンスが詰まっている。
スライド 13 / 15

その後: チューリング

最後に、「その後」の話をしましょう。

まず、先述したイギリスの数学者で、空想上の計算機「チューリングマシン」を考案したアラン・チューリング。彼はチューリングマシンを考案したのち、イギリスからアメリカに渡り、ラムダ計算(弁当箱)を考案したチャーチのもとで学びました。

チューリングマシンを考案した
アラン・チューリングは、
ラムダ計算(弁当箱)を考案した
チャーチに弟子入りした

その後チューリングはイギリスに戻り、第2次世界大戦でドイツ軍の暗号通信「エニグマ」を解読しました。その後、彼は人工知能の分野でも先駆的な役割を果たし、「人工知能の父」とも呼ばれるようになりました。

チューリングは「人工知能の父」に

チューリングは同性愛者で、当時のイギリスでは同性愛行為が違法でした。ある日、若い男性との性的関係を持ったことが発覚し、チューリングは有罪になりました。彼は薬品投与による「化学的去勢」を受け続け、42歳になる直前に毒物を服用して亡くなってしまいました。

チューリングが亡くなってから55年後の2009年、英政府はチューリングに対する迫害を謝罪し、2013年には亡きチューリングに恩赦が与えられました。

そしてこの記事の執筆中、2019年7月15日に、イギリスの新しい50ポンド紙幣の肖像にチューリングが採用されることになったのです。その50ポンド紙幣には、彼が考えた空想上の計算機「チューリングマシン」のイラストが載っています。(参考: BBC)

スライド 14 / 15

その後: ラムダ村

ではその後、ラムダ村はどうなったかというと…

村人たちは、何でも計算できる弁当箱を村の外の人たちに売りさばき、大金持ちになろうと悪巧み中です。

弁当箱は何でも計算できるから、
高く売れる!がっぽり稼ぐぞ!

悪魔は暇になったので、日々ミニオンに新しい芸を覚えさせようとしていますが、なかなかうまくいっていません。

ミニオン、「おすわり」しなさい!
何度言ったらわかるんだ!

そして、年頃になったサヤちゃんは、好きなアーティストのコンサートにもっと参戦したいからと言って、ラムダ村を出ていきました。

今日も自担が尊い〜

以上でおしまいです!ラムダ村の名前の由来も、今回お分かりになったかと思います。ここまでお付き合いくださり、本当にありがとうございました。

スライド 15 / 15

プログラマの方へのメッセージ

本稿をお読みになったプログラマの方の中には、「これはプログラミング未経験者にとっては難しすぎるのではないか」と思われた方もいるかもしれません。そんな方に伝えたいことがあります。

ありがとうございました!

お疲れ様でした!本稿に対するご意見・ご感想を、ぜひ下のツイートを引用リツイートしてご共有ください。

また、本稿の内容について質問がございましたら、上のツイートにスクリーンショット付きで返信してくだされば最優先で対応します。メール(shu@chibicode.com)でもお答えできますが、返事が遅れる可能性が高いです。


本稿を読んで、「プログラミング未経験者だけど、コンピュータサイエンスを学びたくなった。次は何を読めばいい?」と思ってくださった方へ:

次は何を読めばいい?

プログラミング抜きに、コンピュータサイエンスを学べる教材が他にもあればご紹介したいのですが、現時点では筆者がおすすめできるものが見つかっておりません。

というわけで、一定数の方がリクエストしてくださったら、続編を書こうかなと思っています。続編を書くとしたら、人工知能についてプログラミング抜きに学べる教材を作りたいと考えています。

続編を書くとしたら人工知能について

続編をリクエストしたい方は、以下のツイートの引用リツイートで「続編が読みたい」と書いてくださると嬉しいです。


読みやすくする工夫: 難しい内容の教材でも最後まで読んでもらう工夫についてもまとめました。本稿で多用した工夫ばかりです。よければご覧ください!


宣伝: もしご興味があれば、わたしが共訳した書籍『ファクトフルネス』や、わたしのブログもご覧ください。

ファクトフルネス

重ね重ね、本稿をお読みになってくださりありがとうございました!

著者: 上杉周作 (ブログはこちら)
公開日:
ソースコード: GitHubで公開中

読者の声 (抜粋)

みなさまコメントありがとうございます!

上級その5
プライバシーポリシー · 当サイトについて· Twemoji