i7_yoc's something

ぼちぼち生活してます。

(その1?) (分析)哲学者は何をしているのか？？

こんにちは！！！

今日は表題のとおり、「(分析)哲学者は何をしているのか？？」というテーマについて書いてみようと思います。 哲学を専攻するというとたぶん多くの人は頭にクエスチョンマークが浮かんだりすると思います。家族にも「哲学ってどんなことをやるの？？」と聞かれましたし、学問的な興味を共有してきた友人たちにすら、自分が今何を勉強しているのか上手く説明できていないような気がしています。 なので、「どんなことをやっているの」と聞かれたときに見せる用の何かを作りたい、という動機もあり、ゆるく記事を書いてみることにします。

ひとことに哲学といってもその中には様々な分野があり(数学の中に代数、幾何、解析があるように)、その中のすべてを網羅しているわけではないので、今回は僕が興味を持っている形而上学的な分野について、具体的な事例を説明してみようと思います。

※なるべく簡単に書こうとしましたが、引っかかるであろう点をいろいろと回収していったら正確ではないのに難しいという中途半端な記事になってしまいました。ごめんなさい。理解できなかったらなんとなく雰囲気を感じてもらえるだけでもうれしいです。

性質の実在論争

世界には様々な「もの」が存在しています。例えば、りんご、机、火星…といったものです。 ただ存在しているだけでなく、これらの間にはある種の類似性を見出すことができます。例えば、りんごとトマトは「赤い」という点で類似していますし、僕と太郎君(どこかに存在するとしましょう)は「身長が175cmである」という点で類似しています。 ここで問題となるのは、この「類似性」をどのように説明するか、という点です。この点に関して伝統的に、哲学的立場は二つに分かれてきました：

・実在論(realism)…りんごや机といった具体的、個別的な存在者に加えて、「赤い」や「身長が175cmである」という抽象的、普遍的な「性質」が存在する。類似性は、同じ性質を例化(instantiation)している、と説明される。
・唯名論(nominalism)...そのような抽象的、普遍的な「性質」は存在せず、りんごや机といった具体的、個別的なもののみが存在する。類似性は別の方法で説明される。

実在論にはいくつかのメリットがあるように思えます。例えば、類似性を直観的に説明できることです。より詳細な議論も諸論文で論じられていますが、あまりテクニカルになってもしょうがないので、ここでは省略します。

実在論に対して、例えば「性質が存在するといっても、いったいどこにそれがあるのだろうか？？少なくとも物理学などでは、そのような「赤さ」そのものなどの存在は導かれない(言えるのはせいぜい、「波長x(μm)の光が存在する」ということだけ)のではないか？？」という疑問が浮かぶかもしれません。しかし「波長がx(μm)である」というのもまた一種の性質であり、結局はそれをどのように説明するのか？という問題が残ってしまいます。

一方で、唯名論はどのように類似性を説明するのでしょうか？これにも複数の応答がなされていますが、そのうちの一つを紹介してみましょう。一つの例は、クラス唯名論と呼ばれる立場です。これは例えば、「赤さ」という性質を、「赤いもの全体からなる集合」として定義しよう、という作戦です。例えば、集合Redを、Red={りんご、トマト、人間の血、...}というように定義します。すると、りんごとトマトの間の「類似性」は、「同じ集合に属していること」として説明されます。この立場は集合の存在こそ主張しているものの、「赤さ」は何か独立した存在者ではなく、ただの具体的対象の集合に過ぎない、ということになります。

この立場は「赤さ」というような抽象的な存在者を措定しないでよいというメリットもありますが、デメリットもあります。その一つが「共外延問題(co-extension problem)」といわれる問題です。例えば、世界で最も黒い塗料とされるペンタブラックをめぐって、芸術家のアニッシュ・カプーアがペンタブラックの「芸術分野における独占使用権」を購入し、物議をかもしたことがあったそうです(参考1, 参考2)。ここで、次の二つの性質を考えてみましょう：

(性質1) 「2015年に作られたペンタブラック色のものである」

(性質2) 「2015年にカプーアによって作られたものである」

このとき、この二つの性質に当てはまる対象は同じはずです。つまり、性質1に対応する集合も、性質2に対応する集合も同じものなはずです。ここで、クラス唯名論者によれば、性質は集合によって定義されていたので、性質1と性質2は同一の集合ということになります。

しかし、性質1と性質2は、性質としては別物であるように思えます。なぜなら性質1は色についての性質であり、性質2は作者についての性質だからです。これらについて言えることはせいぜい同値な性質であるというだけで、同一であるとは言えないでしょう。このようにクラス唯名論に対しては「異なる性質に対応するクラスが一致してしまう」という反論ができてしまいます。

グルーのパラドックスと自然種

次に用いる例は、帰納的推論にまつわる例です。通常、帰納的推論といえば、次のような推論を指すと思います：

(仮定1) 1個目のエメラルドの色はグリーンだった。
(仮定2) 2個目のエメラルドの色はグリーンだった。
........
(仮定n) n個目のエメラルドの色はグリーンだった。
(結論) すべてのエメラルドはグリーンである。

ここまではよいでしょう。このような推論は我々が特に科学において行っていることです。一つ重要な概念を挙げておくと、この場合、観察されたグリーンのエメラルドは仮説「すべてのエメラルドはグリーンである」を支持するといいます。これは簡単に言えば、私たちがグリーンのエメラルドを見たとき、それは私たちの「すべてのエメラルドはグリーンである」という仮説のもっともらしさを高めている、ということです。

さて、ここで「グルー」という色を定義してみましょう。グルーは次のような色です：

Xの色はグルーである↔Xは2025年以前に初めて観測されその色はグリーンである、またはXは2025年以前に観測されておらず、その色はブルーである

さて、上で述べた観測が2025年以前に行われたものだとしましょう。このとき、「1個目のエメラルドはグリーンである」ならば、そのエメラルドは定義から「グルーである」ことにもなります。すると、次のような帰納的な議論を行うこともできるように思います：

(仮定1) 1個目のエメラルドの色はグリーンだった(=グルーだった)。
(仮定2) 2個目のエメラルドの色はグリーンだった(=グルーだった)。
........
(仮定n) n個目のエメラルドの色はグリーンだった(=グルーだった)。
(結論) すべてのエメラルドはグルーである。

ここで注意したいのは、一つ一つの観測結果に対しては「グリーンだった」と「グルーだった」は同じことですが(観測が2025年以前に行われていると仮定しているため)、結論の「すべてのエメラルドはグリーンである」と「すべてのエメラルドはグルーである」は違うことだということです。もし「すべてのエメラルドはグリーンである」が正しければ、2025年以前に観測されていなかったエメラルドもすべて緑だということになりますし、「すべてのエメラルドはグルーである」が正しいならば、2025年以前に観測されていなかったエメラルドは青いということになります。

私たちは通常、「k個目のエメラルドの色はグリーンであった」という観測結果は、「すべてのエメラルドはグリーンである」は支持するが、「すべてのエメラルドはグルーである」は支持しないように考えます。(エメラルドを見て、「じゃあ2026年に観測されるエメラルドは青いな！」と考える人はいませんよね)。しかしなぜ、この観測結果はどちらにも合致するのに、一方だけを支持するのでしょうか？

最初に考えられる説明は、「グルーはグリーンを用いて定義されているから」というものです。ですがこれに対しては、次のように応答することができます：

まず性質「ブリーン」を「グルー」と同じように定義します：つまり、Xがブリーンであるとは、Xが2025年以前に初めて観測されてかつブルーであるか、2025年以前に観測されずグリーンである場合です。

そうすると、今までの「ブルー」や「グリーン」を、「グルー」や「ブリーン」を用いて再定義できるようになります：例えば、「グリーン」は「2025年以前に観測されておりブリーンだった、または2025年以前に観測されておらずグルーである」というように定義できます。この場合、双方が双方を用いて定義できるため、一方がもう一方より基本的だといえる理由にはなりません。(本当は図を書いて説明したかったのですが、なぜかペイントがクラッシュしたので断念。)

別の候補は、「すべてのエメラルドはグリーンである」方が過去と未来の類似性を保てる、というものかもしれません。しかしどのような類似性でしょうか？もしそれが「緑である」という類似性ならば、「すべてのエメラルドはグルーである」の場合も過去と未来の間に「グルーである」という類似性を見出すことができ、結局先ほどと同じような問題に帰着してしまいます。

とはいえ全く解決策がないわけではありません。一つの解決策は、グリーンは「自然種」であるが、グルーは「自然種」ではない、というものです。自然種とは、世界の普遍的な構造を記述するために用いられる性質、と大雑把に捉えておきましょう。

なぜグリーンは自然種で、グルーは自然種ではない、と言い切れるのでしょうか？例えばクワイン(Quine)は、次のように述べています：

帰納法に世界の真理へアクセスするための方法としての信頼を置くことは、私たちの質的空間(quality space)が宇宙のそれと対応していると仮定することに他ならない。

質的空間とは、私たちがどのようにして質(=色の感覚など)を分類するか、ということです。クワインは、私たちの感覚的な分類が、実際の世界の分類に対応していると考え(これは例えばダーウィンの進化論などで正当化が得られるかもしれません)、グルーを排除しています。

正直に言うとこのクワインのエッセイ("Natural Kinds")は初めて読んだときにあまり理解できておらず、今でもまだしっかりとはわかりきっていないので、誤っている点があるかもしれません。そしたらごめんなさい…

※一つ注意をしておくと(これはクワインも指摘していることですが)、この記事内では「赤さ」や「グリーン」といった色の例を用いましたが、これに違和感を感じる人もいるかもしれません(例えば「赤」は様々な波長の光を含むので曖昧だ、みたいな)。これは単に議論を簡素化するための目的で行ったので、必要であればほかのより「科学的に正確な」性質に置き換えて考えてみてください。

おわりに

いかがでしたでしょうか？本当はあと1～2個くらい具体例を挙げたかったのですが、一つの例について正確なことを書くのも思ったより大変だったので、今回はいったんここまでとします。記事の題名が「(その1?)」になっているのはそういう理由です。

初めにも書きましたが、なんとなくでいいから僕が普段どんなことを学んでいるのか、というのを理解する一助になればうれしいなと思って書いたので、その目的が果たされていることを願いましょう。そのうち気が向いたら別のトピックについても書くかもしれません。

では！！！

参考文献など

Ney, Alyssa (2014). Metaphysics: An Introduction. New York, NY: Routledge.

Armstrong, David M. (1991). Properties. In Kevin Mulligan (ed.), Language, Truth and Ontology. Dordrecht, Netherland: Kluwer Academic Publishers. pp. 14--27.

Goodman, Nelson (1955). Fact, Fiction, and Forecast. Philosophy 31 (118):268-269.

Quine, Willard V. (1969). Natural kinds. In Willard Van Orman Quine (ed.), Ontological Relativity and Other Essays. New York: Columbia University Press. pp. 114-38.

アメリカ生活所感(2024-10)

こんにちは！

留学し始めて3か月が経ったので、少し所感みたいなものをまとめてみようかなと思います。(そういえば前回書いた記事の続きもまた公開できてませんでしたね、1万字くらいの下書きを7月に書いて以降放置ですみません...)

学業

えーと、まず初めに専門を変えて今は数学科ではなく哲学科だということを注記しておきます。

で、怒涛の勢いで論文を読まされます。1週間に合計100ページは英文を読んでいると思います。TOEFLの長文で悲鳴を上げていたあの時はまだまだ甘かったな、と。内容としては現代哲学の礎になっている論文(例えばQuineやLewis, Popperなど、1950-80年代のものが多い)を週に3～5本ほど。

授業は今期はMetaphysics(形而上学)、Phil. of mind(心の哲学)、Phil. of science(科学哲学; ディスカッション)をやってます。日本の大学だと1週間に一度100分程度の授業がある形態が一般的だと思いますが、こっちは50分授業×週3または75分授業×週2で行います。トータルの授業時間が日本より多い、かつ一度に詰め込み過ぎない分かなりテンポよく進み、それでいて理解もしやすいので、自分はこっちの形態の方が好きですね。ディスカッションだけは2時間半の長丁場が週1という感じで、議論しているとついつい時間が経過しがちなので、これはこれでうまくできているなと思います。

基本的にはどの授業も、中間レポート(double spaceで5ページ程度)、期末レポート(10ページ程度)が課されます。それに加えて試験がある授業もあります。今のところレポートはすべて最高評価もらえてるのでまあ成績に関してはいい感じといっていいのでしょう。

あと、基本的に講義スタイルではあるのですが、学生とのやり取りが日本の授業より多いなと思います。まあこれは数学と哲学の学問的な性質の違いにも起因すると思うので、一般的な日米の違いと呼べるかはわかりませんが。

TA

TAとはTeaching Assistantの略です。日本の院生でもTAをしている方はいると思います。

僕はLogic(論理学)の授業のTAなのですが、まずこの授業も例外なく50分×週3のスタイルです。そして月曜と水曜は教授が授業を行い、金曜日の問題演習(Drillと呼んでます)が僕の担当です。ほかには課題や試験の採点も行います。日本の友人曰く試験の採点は日本では博士号を持っていないとできないようなので、こういうところにも日米の違いが出るんですね。

学部時代は個別指導塾でアルバイトをしていたのですが、集団になるとやはりついていけない生徒も出てくるので、どうフォローしようか悩みます。大学の授業にもなると、一定数が理解してくれているから、と割り切ってしまうのも重要なのかもしれませんね。論理学は哲学の中でもかなり数学に近い分野なのですが、そもそもアメリカの大学入試で用いられる数学(SAT)は日本の高校入試並みの難易度だと聞いたこともあるので、複雑な式や論理を扱う訓練を受けていない、という問題もあるのかもしれません*1。

TAをやる理由として一番大きいのは、TAが生活費支給＆授業料免除の条件になっているからです。ちなみにアメリカの院、特にPhD(博士)プログラムは多くがこのシステムを採用しています。Master(修士)だと自分で金銭的負担をしなければならない箇所もありますが、自分のところはMasterにもお金が出ます。あとはTAを経験することはPhDや研究職への出願の際に有用という話も聞きます。真偽は知りませんが。

英語

最近は専門分野に関する話題ではむしろ英語の方がすらすら出てくるようになり、逆に日本語で思考しようとすると違和感を感じるようになってきました。一方自分自身が割と内向的なタイプの人間なのもあり、世間話などはそこまでたくさんはしないので、日常の出来事とかは日本語で思考している感じです。

高校時代そこまでまじめに英語を勉強していなかったせいで、今でもたまに英文法がわからなくなります。「あれ、これってどの語順が正しいんだっけ？？」(特に疑問文がらみとか)ってなってよくフリーズします。あと普通に論文とか読んでいてもわからない単語やイディオムが多いので、まだまだ英語についても勉強する余地はあると思います。高校時代は「C言語できる(※そんなにできません)んだから英語できなくてもええやろ！！」とか思ってましたが、なんだかんだちゃんとした英語を話せないと言いたいことも言えないですからね。

文化

世間話って何でしょう？？自分は日本人とすら世間話の話題を見つけられないので当然アメリカ人とも話す話題がないな～～と思ってしまうわけですね。この辺は多分自分の感覚がおかしいだけで、自分が世間一般の娯楽と無縁に生き過ぎたせいで一般的な話題がないわけです。そもそも人生つまらん！！って思っていた頃(中学生辺り)に価値を見出せた数少ない興味を突き詰めた結果が今の大学院での研究なので、それ以外のことにあまり興味がわかないどころか面倒だと思ってしまいます。趣味はありますがそこから一般的な話題に広げられるようなものではないし、ゲームとかはたまにやるけどたくさんはやらないし、、、

周りの話を聞いてるとこっちでの一般的な話題はスポーツ(MLB, NBA, 大学スポーツ:特にアメフト)とか音楽や映画といった文化とかが多いのかな...?? もう少し一般的な娯楽を知った方がよいのかなと思う今日この頃です。一回日本のアニメの話が聞こえてきたことがあったけどワンピースも鬼滅も呪術廻戦も観てなくてよくわからなかったので*2、日本人としての常識もないのかもしれません。つまらんやつでごめんよ。

先週MLBを見てみましたが(ドジャースvsパドレス)、大谷翔平が普通にホームランを打ってて、ああ日本でも騒がれていたのはこういうことなのかぁと納得。エネルギーを消費しすぎない範囲でもう少しそういう娯楽を嗜む機会を設けてもいいのかもしれませんね。

今後

今は修士1年目ですが、来年は博士課程の院試がまたあるので、とりあえず修士の間の目標はそこでよい結果を残すこと、です。学生の論文発表のための機会もたくさん設けられているようで、1年生のうちに最低1回は何か形に残る成果を出せればいいな、と思っています。

今回はアメリカ生活がどんな感じかという一般的な話題に焦点をあてて書いてみましたが、そのうち自分が今行っている勉強やこれから行うであろう研究に焦点を当てた記事も書いてみたいなと思います。あとは学部生活振り返り編の続編ね。

*1:日本の高校生と比べてアメリカの高校生の勉強時間は一般的に短いと思います。塾で夜遅くまで勉強なんてしません、そもそも塾がないからです。それでよく社会が回っているなという印象を受けたのですが、最近のアメリカ社会の抱える構造的問題を考えると、必ずしも社会がうまく回っているとは言い難い一面もあるのかもしれません。この辺りの主張をするにはもっと強い根拠と深い洞察が必要そうなので、今は深入りはしないでおきますが。

*2:ぼざろと僕ヤバは面白かったです。

数学科首席の取り方<Part1>

数学

ご無沙汰しております。タイトルで書いた通り某大学数学科を首席(=学部最優秀賞)で卒業しました。卒業から多少時間が経ったこともあり、大学生活を浅くまとめた記事を書いてみようと思いました。あとで見ると恥ずかしくなりそうなタイトルですが、まあいいか。

今は新しい環境へ移る準備を進めていて、其処に適応できたらまたその話も書こうと思いますが、とりあえず今は別の話。日本を離れ、海の向こうが次の舞台になる、という予告だけしておきます。

書いていたら結構長い記事になりそうなので、とりあえず今回はPart 1として入学前の話を書こうと思います。Part 1はなぜ僕が数学科に入ろうと思ったかという話と、僕の学部生活をこれ抜きで語ることはできないであろう留学願望の話です。

Youは何しに数学科へ？

最初の興味はAI

もともと人間の思考というものを分析することに興味があり、正しい思考とは何か、何かを志向する・表象するということがどうして可能なのか、またそもそも意識的に世界を知覚できるのはなぜかといった事柄に興味がありました。これらは脳で発生しているアルゴリズムとして多かれ少なかれ理解されるだろう、ということで、最初に興味を持ったのが機械学習、とりわけニューラルネットワークでした。 これは僕が高2のとき(=2018年ころ)の話で、当時は(今もですが)世の中が少しずつニューラルネットワークすげー！ということを理解し始めた時代だったように感じています。うろ覚えでなければ深層学習が登場したのが2014年ころの話だったと思っていて、それがいろいろな成果を上げて注目された、といった感じだった気がします。

まあともかく、人間の脳の構造を模したといわれる(といっても今となっては鳥と飛行機のような関係なのかもしれませんが)ニューラルネットワークが成功を収めていたことは僕にも少なからず影響を与え、こういうものを研究していけば僕が真に知りたかったことがわかるのではないか、という動機で機械学習の勉強を始めてみました。今でも、誤差逆伝播法、とかそういう機械学習関連の用語を聞くと、必死に勉強していた当時を思い出して懐かしくなります。

ちなみに、そういうモチベーションならなぜ神経科学とかに行かなかったのか？と問われそうですので答えておきます。理由はいくつかあるんですが、その中でも神経科学=ハードウェアの研究、ニューラルネットワーク=ソフトウェアの研究というイメージが自分の中に在ったこと、独学しやすいのが後者だったこと、そして当時競技プログラミングをやっていてコンピューターサイエンス系に進みたいと思っていたことが大きいかなと思います。もちろん心理学などと連携したソフトウェアサイドの脳神経科学の研究もあるでしょうし、逆に機械学習もすべてがソフトウェア研究ではないと今になってわかりますが、当時の大学見学の経験などを考えるとこのようなイメージがついてしまったのも致し方ないのかなと思います。あとは似た話ですが、実験より理論研究をしたいなという考えもあったかな。

数理論理学へ

同じころ、思考の正しさという話題についてはコンピューターサイエンス的な観点以外からも考えていました。具体的には、より原理的に、ある思考は何をもって正しいといえるのだろう、ということを考えていました。僕ら人間が、あるいは少なくとも僕が普段考えていることで、正しそうなことはたくさんあると思いますが、「これは絶対的に、確実に、何があっても正しい」といえることはなかなかなさそうですよね。でももし世界の真理というものがあるのならば、それは後者に属するはずですし、また僕は思考の中でもとりわけそのような対象に興味がありました(今もあります)。そしてそういった思考の題材に最適なのが数学だった。なぜなら数学的な命題はさっき書いた「これは絶対的に、確実に、何があっても正しい」というような事柄だと思えたからです。

このようなきっかけがあって、「数学的な各命題はなぜ正しいといえるのだろう？」ということを考えるようになりました。例えば数学の教科書を読んだり答案を書くときにも、一行一行に書いてあることに対して「こういうことが言えるのはなぜだろう」と疑い、「これは一般的に成り立つ○○の定理に具体的な数を当てはめるという操作をしていて、一般的な規則に具体的な対象を当てはめることは確かに正当化されるからこの内容も正しいのか」「これ(累積帰納法)は確かに正しそうに見えるけど、通常の帰納法を使ってこれをしっかりと正当化できないだろうか」とかそういうことを考えていました。そんなことを考えているうちに、結局数学はどこかで確実に正しいといえる事柄があって、そこから適切な推論を行って帰結を得るということ(=証明をすること)で正当性を保証しているのだ、ということに気が付きました。余談ですが、この頃担任だった数学の先生から「最近○○(僕)は記述を2倍くらいの量書くようになったね」といわれたのを覚えています。それも多分こうやって、正当性をこれでもかというくらい気にしていたからだったのでしょう。

同じころコンピューターサイエンスの方も、独学で学んでいた人工知能であまりいいものが作れなかったこと、および自分が興味があるのは「なぜこのような回路・ダイナミクスによって思考や意識といったものが生まれるのか」という原理的な問いを解明することであり、実際の諸モデルなどにそこまで興味があるわけではなかったことなどから、実際に人工知能に関わるというよりはむしろより原理的な側面から探究をしたいと考えるようになりました。特にニューラルネットワークのような構造は数学的に記述され解析される対象であるので、その数学的記述を研究することにより上に書いたような問いに近づけるのではないかと考えました。つまり自分が本当にやりたかったことはコンピューターサイエンスではなく、その理論の本質ともいえる数学でどのように世界が説明されるかを探究することだった、ということに気づいたのです。

当時高3で進路選択の時期が迫ってきていたので*1、上のような要因もあって数学方向に視線を向けるようになりました。大学には数学科と応用数理学科があるのですが、興味はコンピューターサイエンスなどと重なる部分も多く、また代数や解析も面白そうではあるもののメインで取り組みたい問いというわけではなかったため、当時は応用数理学科に進学しようかな、と考えていました。

で、大学の学部説明会に行ってみるわけですが、ここで奇遇にも*2学部時代の指導教官が数学科の担当でした。その先生の専門分野であった数学基礎論という分野は今まで聞いたことがなかったのですが、数学の証明やメタ的な側面が研究対象だと聞いて、自分の考えていたことに深く共鳴する感覚がしました。

夏休み前に、数学基礎論関連で読みやすくかつしっかりした内容の本がないかなぁ、と淡い期待を込めて本屋に行きました。そこでピックアップしたのが結城浩先生の『数学ガール　ゲーデルの不完全性定理』です。詳細はぜひ本を読んでほしいのですが*3、例えば数学の定理がすべて公理と推論規則を用いて証明されるということ(もっと言えば、公理という「確実に正しいといえる事柄」が本当にどこかにあったこと)など、自分の思い描いていた世界観通りに数学が在るということに感動し、この分野をもっと学びたいという意志のもと、数学科に進学することを決意したのでした。でも今にして思えば、数学基礎論の僕にとって一番おいしいところを楽しめたのはこの時期だったな、という気もします。この先基礎論という分野が実際にどういうものなのかを知っていくにつれ、また少しずつこの分野から離れていくことになるのですが、それはもっと先のお話。

つまり、単にひたすら計算や証明を行って数学的真理にたどり着きたいから数学科に来たのではなく*4、むしろ数学というものがどのようなものなのかを理解するために数学科に来た、というわけです。

この時点で既にそれらしい気配は出始めていますが、大学卒業後のこれからは、数学の道からは少し離れて探究を続けていく予定です。まあでも、これも今後の記事で書く予定ですが、数学とは何かというルールブックがすでに手中にあり、かつこの後言及するように競技科学・数学を通じて数学固有の思考(計算やテクニック)に慣れていたので、数学科というゲームにおいては高得点を出すプレイヤーになれたのかな、と思っています。

競技科学と自分の能力

色々あって高校生になったころに友達から競技プログラミングの存在を知り、打ち込む日々を送っていました。詳細は当時の記事(これとか)に譲りますが、情報オリンピックやパソコン甲子園といった大会で本選に進むために、授業中も部活でも修学旅行中でも夢の中でも競プロのことを考えていました。落とされた経験もありますが、最終的にどちらも本選に出場することができ、全国レベルで戦える実力をつけることができました。

競技者として常に精進し続ける日々が辛くなかったといえばそれは嘘になります。しかし何かを残そうと必死に足掻いた結果、成功体験というかけがえのない経験をすることができたのは、この日々が僕に残した意味のうちの大きな一つなのではないかなと思います。この経験があったからこそ、この物語の続きの部分にも書きますが、ただ自分がやりたいというだけで難題に突っかかっていくことができました。数学科に進みたいと思ったのは上に書いた要因が理由ですが、進めると思ったのは、競技科学を通じて、僕が一つの問いにとことん向き合い続けることができる人間だということが分かったからです。

留学経験と留学願望

上の話と並行して、高2の夏にバンクーバーに短期留学をしていました。1か月もないくらいの期間でしたが、向こうの風土や生活感をすごく気に入って帰ってきました。それから、いつかはこんな街に住んでみたいなというふわふわとした夢が頭の中をさまよっていました。 ある朝電車に乗っていて、なんとなく将来のことを考えて物思いに耽っていたのですが、その朝はすごく清々しい天気で、ふとカナダの景色が頭によみがえりました。そこでふと頭の中で点と点が繋がって線になり、「海外で研究者を目指したらどんな未来が待ち受けているのだろう…??」ということを考え、スマホで「海外　大学院　留学　数学」みたいなことを調べました。すると実際に海外大学院(UC Irvine)を出て研究者をされている方のブログ(こちらです:

snowtotoroblog.com

)が見つかりました。このブログにすごく感銘を受け、勇気づけられたことを覚えています。 海外の大学院に進学することは実力的にも不可能ではないこと、そして多くの場合奨学金により学費免除・生活費支給が受けられるため経済的にも不可能ではないことがわかり、それだけでも志望するには十分な動機でした。この後大学での学びを通じて海外を志望する理由はほかにも生まれてきますが、そもそものきっかけはやはり海外に憧れがあったからなんだと思います。いま記事を書いていて、(この頃思い描いていたものとは多少の違いはあれど)この憧れていた先の世界を実際にこの目でこれから確かめに行くということを改めて実感して興奮してしまいました。

次回はPart 2として、大学1~2年生の話を書こうと思います。引き続きよろしくお願いします！

*1:大学は内部進学で進んだので、どの大学に行くかは考える必要がなく、むしろどの学部に行くかが問題でした。

*2:自分の人生において、運命の出会いというものはなんだかんだ数回はあると思うのですが、これもその一つだと思います。

*3:物語風に書かれているので、数学書を読んだことがない人でも比較的読みやすいと思います。もっとも一応数学科首席を取った人間が読みやすいと言っても信憑性があるのかわかりませんが...

*4:もちろんそのようなモチベーションを蔑んでいるとかそういうことではありません。ただ僕がそうでなかったというだけで、そのような期待をもって数学科に来るのはむしろ健全な動機だと思います

モデル理論の面白い命題をちょっと紹介【Wathematica Advent Calendar 2022】

数学

この記事はWathematica Advent Calendarの7/6の記事です。(ところで何をAdventしているのだろうか...?)

こんにちは！現在数学科3年のinaです。

皆さんは数学基礎論という分野をご存じでしょうか？大雑把に言うと数学基礎論は「数学」というシステムそのものを考察対象とする数学の分野のことです。(故にメタ数学なんて呼ばれることもあるようです。) ゲーデルの不完全性定理なんかは名前を聞いたことがある、という方も多いのではないでしょうか。

数学基礎論はさらにいくつかに細分することができますが、今回はその中の「モデル理論」という分野をすこ～しだけ紹介したいと思います。

記事中に出てくる証明は読み飛ばしても大丈夫です。証明を追うというよりはむしろどんな命題があるか・それは何を意味するのか、を理解していただけたら嬉しいです！

モデル理論とは？

数学基礎論では、数学における「命題」を形式的な記号列("文"や"論理式"とよばれる *1 )にして扱います。この辺は細かい話は省略しますが、例えば

任意の\epsilon > 0に対してあるn_0 \in \mathbb{N}があり、任意のn \in \mathbb{N}に対して、n>n_0ならば|a_n-a|<\epsilonである

という命題を論理式化すると、

\forall \epsilon > 0 \, \exists n_0 \in \mathbb{N} \, \forall n \in \mathbb{N}[ n>n_0 \rightarrow |a_n-a|<\epsilon]

といった具合です。*2

さて、今作ったような論理式はあくまで"記号の列"であって、それ以上でもそれ以下でもありません。ですが例えば上に書いた記号列を見たとき、「この記号列は数列の収束を表しているんだな」と捉える人が多いはずです。これは、ただの記号の並びを実際の数学的な対象に対応づけていると考えることができます。この対応付けのことを「解釈」とよびます。

ここで重要なのは、解釈は一通りではないということです。例えば上の例では数列の収束以外の解釈は思い浮かばないと思うので、もう少し簡単な例を用意してみます。

\forall A \forall B[A \leq B \lor B \leq A]

この論理式の場合、次のような解釈を行うことができます:

① A,Bは実数、 \leqは実数の通常の大小関係(この場合この命題は真)

② A,Bは集合、 \leqは集合の包含関係(つまり通常は A \subset Bと書くようなものを記号を取り換えて A \leq Bと書いたということ。この場合命題は偽)

③ A,Bはグラフの頂点、 A \leq Bは Aを始点、 Bを終点とするパスが存在することを表す(この場合の真偽は考えているグラフによって異なる)

論理式が真になるような解釈のことを、論理式のモデルと呼びます。

コンパクト性定理

ちょっと強い定理を紹介します。(数学基礎論における)コンパクト性定理とは、以下の命題のことです:

\Gammaを文の集合とする。この時 \Gammaがモデルを持つことと、任意の \Gammaの有限部分集合がモデルと持つことは同値。

証明はGödelの完全性定理*3を認めてしまえばすぐにできますが、一回省略します。コンパクト性定理を認めたうえで、次の定理を証明してみます:

\Gammaを文の集合とする。 \Gammaがいくらでも大きい有限モデルを持てば、 \Gammaは無限モデルを持つ

(証明) 以下のような文たちを考える:

\phi_2 : \exists v_1 \, \exists v_2 [v_1 \neq v_2] (…"最低2個は元がある"みたいなことを指し示す)

\phi_3 : \exists v_1 \, \exists v_2 \, \exists v_3 [v_1 \neq v_2 \land v_1 \neq v_3 \land v_2 \neq v_3] (…"最低3個は元がある"ということ)

のように \phi_n \, (n\in\mathbb{N})を定義する。*4

集合 \Gamma_0 = \Gamma \cup \left( \underset{n \in \mathbb{N}}{\bigcup} \phi_n \right)を考えると、 \Gamma_0の任意の有限部分集合はモデルを持つことがわかる。よってコンパクト性定理から、 \Gamma_0もモデルを持つ。これは少し考えると有限モデルとはなりえないことがわかる。(証明終)

次にこの定理の帰結として、次のような面白い事実を紹介します。

有限と無限の区別はできない？

前の定理から、例えば次のような帰結が得られます:

任意の有限群で成り立つが、任意の無限群で成り立つような等式は存在しない

(証明) 群の元に関する等式 \phiを任意にとる。群の3公理を論理式化したものをそれぞれ g_1, g_2, g_3とし、 \Gamma = \lbrace g_1, g_2, g_3, \phi \rbrace とする。

\phiが任意の有限群で成り立つなら、 \Gammaはいくらでも大きい有限モデルを持つ。よって \Gammaは無限モデルを持つので、これは \phiが成り立つような無限群が存在することを意味する。*5(証明終)

何が言いたいかというと、群の元の等式だけでは有限群か無限群かを区別することはできないのです！こういうように、数学の命題について主張できるのは数学基礎論の面白いところだと思っています。

※「Gは有限群である」という命題で有限群と無限群を区別できるのでは？と思われる方がいるかもしれませんが、今回の主張はあくまで「群の等式は存在しない」と言っています。(つまり例えば aba^{-1}b^{-1}=eといった等式で、任意の有限群で成り立つが任意の無限群で成り立たないものは存在しないという意味です。) 「Gは有限群である」というのは集合論的な主張(有限と無限の定義など)を含んでいて、この場合モデルとしては群というよりむしろ集合論("集合"ではなく"集合論")を考えることになってしまいます。

Löwenheim-Skolemの定理

もう一つほどモデル理論のいい話を紹介したいのですが、そのためにLöwenheim-Skolemの定理と呼ばれるこれまた強い定理を紹介します。

論理式に用いる記号の数が可算*6であるとする。このとき文の集合 \Gammaが無矛盾なら、 \Gammaは可算なモデルを持つ。

この定理もGödelの完全性定理からすぐに得ることができます。さっき紹介したコンパクト性定理のときもそうでしたが、つまるところ完全性定理がかなり強いのです(ただし証明も大変)。詳しい人向けに言うと、完全性定理を証明する際に構築するモデルの濃度が文の集合の濃度と同じになるためこの帰結が得られます。

可算の中の非可算…??

この定理から得られるものとして、「Skolemのパラドックス」を紹介します。これは実際には矛盾は生じていないのですが、矛盾が生じていると誤解されがちな例です。

集合論の授業や教科書で、「集合とはものの集まりのことです」みたいなあいまいな説明をされてもやもやした経験はないでしょうか？しかし実は、集合を扱うための「集合論の公理」というものがあります。有名なのはZFC*7と呼ばれるものです。詳細は「公理的集合論」などで調べてください。

集合論の公理(例えばZFC)の文全体を \mathcal{L}^{set} とします。これに出てくる記号の数は可算*8で、またこの公理系は無矛盾であると信じられています*9。よって先ほどのLöwenheim-Skolemの定理から \mathcal{L}^{set} は可算なモデル \mathcal{N}を持ちます。つまり、「集合全体」として可算集合を選ぶような解釈が存在するわけです。

...と、ここで何か気づきませんか？そう、集合は数えきれないほど多くあるのにもかかわらず、集合全体の個数が可算であるような解釈が存在するのです。

もう少し具体的に何が考えてみましょう。例えば集合論の公理からは、「集合は少なくとも非可算無限個存在する」という主張が言えるはずです。しかし、 \mathcal{N}は可算であるにもかかわらず、この文が真になるような解釈なのです。さて、この状況にどうやって対処しましょうか？

これは結構説明が大変なのですが、まずは次のような図を見てください。

ポイントは、" \mathbb{N}から「集合全体」への全単射*10は存在しない”という主張を、どこでしているのかということです。

先ほど述べた通り、可算なモデル \mathcal{N}の中では、集合は非可算個あることが証明できます。一方”集合は可算個”と言っている場合、僕らはそのモデルの「外から」考察を加えているわけです。モデル理論自体も集合論で扱えるので、メタ的な視点からモデルを考えているということもできます。

この辺の話は慣れていない人にとってはちんぷんかんぷんだと思いますし、自分も記事を書こうとして頭がこんがらがり、「本当にわかっているのか...??」と思いました。もしかしたら僕の説明が間違っている可能性もあると思うので、その際はご教示いただければ幸いです。

簡単に要点をまとめると、

①モデルについて考えるということは、「論理式を解釈した世界」について外側から(=メタ的に)考えるということ。

②例えば集合の濃度といったものは、モデルの中で考えるか外で考えるのかによって見え方が異なることがある

ということです。いい話ですね！

おわりに

いかがでしょうか。自分の理解が甘いなと感じるところがあったり、あまりオリジナリティのある内容にはできなかったりと、いろいろ反省しております。割と教科書に書いてあることをそのまま書いてしまった感じが強いので、興味を持った人は下に挙げたEnderton先生の教科書の2.6節あたりを眺めてみてください。

参考文献

[1] Herbert B. Enderton(著), 嘉田勝(訳), 論理学への数学的手引き, 1月と7月, 2020

[2] 『数学基礎論A』(早稲田大学数学科) 講義ノート

[3] 仙台ロジック倶楽部 "数学基礎論と消えたパラドックス" https://sites.google.com/site/sendailogichomepage/files/ref/ref_07, 2022/07/05閲覧

*1:正確には文と論理式は別の概念(特別な論理式が文)なのですが、あまり気にしなくていいです。

*2:本当はこの辺も細かい定義づけが必要なのですが本質でないので割愛

*3:有名な不完全性定理とは全然別のものです。

*4: \phi_1が気になる方は適当に定義してください。(例えば \Gammaの中の適当な文など)

*5: g_1,g_2,g_3を満たすので、 \Gammaのモデルは群になります。

*6:集合が可算であるというのは、簡単に言うと自然数と同じくらいの大きさであるということです。例えば整数や有理数は可算集合ですが実数はそうではありません。

*7:ZFCのCは選択公理と呼ばれる有名な命題のことを指しています。選択公理を認めない立場もあるようで、選択公理を排した公理系はZFと呼ばれています。ZとFはともに人名由来です。

*8:書いている途中ここで"ほんとか...?"となりましたが、解釈するときの各記号への集合の割り当て方が非可算無限通りあるというだけで、記号自体は可算個で済みます。一つの文に非可算無限個の記号が出てくることはないので。

*9:Gödelの不完全性定理があるので、ZFCの無矛盾性は実は証明できないというこれまた面白い事実があります。ほとんどの数学者はZFCが無矛盾だと信じてはいるようですが

*10:集合全体は標準的な解釈によれば集合ではないので、この表現方法はちょっと怪しいです

TOEFL ~その2~

その他

↓これの続きの話です。

i7-yoc.hatenablog.com

さて、前回のTOEFLが終わって半年以上経ちますが、それなりの進捗を出すことができたので記事でも書こうかなと思います。

前回からやったこと

・英単語3800のLv.1~Lv.3を一通り学習

・Listeningのシャドーイングの練習

・Writingの練習

・全体的な演習量の強化

が主な内容です。

単語

TOEFL対策の定番本(らしい)3800をやっと購入。

www.obunsha.co.jp

マイペースなので、9月~12月かけてやっとLv.3まで一周。ネットで色々調べると1か月とか2か月とかで全部回している人もいてすごい。 1回やっただけだと結構忘れます。3周くらいしていますがいまだに7割くらいしか頭に入ってません。携帯アプリの単語帳買って補強しようか迷いましたが結局買いませんでした。

Listening

個人的にListeningを伸ばす一番のコツはシャドーイングだと思います。僕は後述するTPOで練習しました。特に1問目と3or4問目に来るConversationのタイプが苦手なので、このPassageで集中的に練習しました。 あとはノート取りももちろん大事です。コツは、単語を書くことだけに意識が向きすぎてその間の会話を聞き逃さないようにすること。メモは文章である必要はなくて、単語だけで十分です。

Writing

Writingは今まで何故伸びなかったかがわからなかったので、とりあえずトフルゼミナールの問題集を購入。

tofl.jp

これが結構いい本で、なぜ今までのWritingが駄目だったかよくわかりました。一言で言うと、Integratedは構成が不安定で、Independentは具体例が少なく一般論ばかりで作文を組み立てていたことですね。あとは時間がいつもギリギリだったこと。 問題集で基礎演習を積んだり解答例を自己添削した後、ひたすらTPO周回です。

演習量の強化

TOEFLに限らず競技数学・プログラミング(、入試？)など様々なことに言えると思うのですが、過去問を解くことよりも効果のある勉強はないと思っています。 で、どこに過去問があるの？という話ですが、TPO(TOEFL Practice Online)というサービスがあります。これは実は2つのものを指していて、一つはTOEFL公式が提供するプレテスト。1回5000円くらいしますが、公式の採点(ただしSpeakingとWritingは機械採点)が受けられます。もう一つは中国のサービスで、中国人向け？にTOEFLの過去問を公開している場所があります。ですがうまいことやると日本人でも使えます。詳しくは各自調べてみてください。

TPOで成果確認

3月にTOEFLがあるのですが、その前に成果確認がしたかったのと、自信が欲しかったので、2月にTPO(officialな方)を受験しました。

<結果>

日時 Total Reading Listening Speaking Writing
2020/12 66 19 14 16 17
2021/6 80 22 21 20 17
2022/2 103 29 25 21 28

ということで、念願の100点突破！！PracticeなのでUnofficialなスコアとはいえ、とても嬉しかったです。

(Speaking以外は)かなり成果が出ました！とりあえずSpeaking以外の勉強法は正しいとわかったのでこのまま継続。Speakingの対策を集中的に行うことにします。

Speakingの強化

Speakingがあまり伸びなかったので対策。TPOの採点は確かAIがやっているそうです(ちなみに本番は人間メイン+AIがサポート、という形らしい)。本番のスコアがどれくらいになるかは読めない部分もありますが、まあやっておいて損はないでしょう。

対策として、TOEFLのSpeakingは問題ごとに形式が決まっているので、それに応じたテンプレートを作り、実際に使う練習をしました。 具体的には、例えば1問目は短いQuestionが与えられて「Do you agree or disagree with this statement?」みたいな感じなので、テンプレートとしては、

In my opinion, I think that __________.

The main reason is that ____________.

For example, __________.

Another reason is that __________.

For example, __________.

みたいな感じです。これをSpeakingが始まる前にメモ用紙に書いておいて、始まったら穴埋めして読んでいきます。そうすることで、話している最中に全体の構成について考えずに済みます。

スクリプトを用意するときに気を付けるのは、

・ある程度文章の形で書いておく

・できるだけ簡単な・ちゃんと理解している単語を使う

です。

前者についてですが、僕は今までSpeakingの問題をやっている最中に文がうまく組み立てられず止まってしまう、なんてことがありました。それを防ぐために、ある程度文章の形をしたメモを書いておきます。ただし一字一句全部書く時間はないので、自分が見てすぐわかる範囲で適宜省略しましょう。

単語については、難しい単語を使うと話した後で「あれ、これってこの使い方であってたっけ…？」となり、不安になったりわざわざもう一度言い直したりしてしまってあまりうまくいきません(経験談)。なので、自信のない単語は使わない方がbetterです。

他の科目は今までと同じような練習をやってきました。そして3月某日、いよいよ本番！

本番

一番乗りで会場入りするために早めに家を出ます。昼食は軽めにしました。これ結構重要で、睡魔はかなりパフォーマンスに響くと感じています。

Readingは練習では5分くらいしか余らなかったのですが、本番は10分余りました。結構自身もあったのでOK。

Listeningは2or3セクションあるのですが、自分の時は3セクションでした。おそらくどれかのセクションがダミー(採点されずスコアには影響しない)だったのでしょう。最初のConversationと、Section 2のLectureが全然理解できなくて焦りました。あまりベストパフォーマンスを発揮できなかったと感じましたが、これを引きずるわけにもいかないので、気を取り直して後半戦へ。…の前に、Break timeの間にSpeakingのテンプレを作成しておきます。

Speakingはかなり順調で、全部の問題でほぼ止まらずに話し続けることができました。Writingも大きな失敗なく無事こなせたと思います。

唯一間違えたのは会場選びですね。僕は本郷の会場で受験したのですが、仕切りが浅く、Listeningの回答中に隣の人のイヤホンから音漏れしてそちらのLectureが聞こえてしまい、集中力がそがれました。あとWritingが始まったときに周りはまだSpeakingをやっていてうるさかった記憶があります。耳栓を持って行ったのでそれをつけながらやりましたが、やはり静かなのにこしたことはないです。会場選びもネットで調べればもっと色々出てくるはずなので詳細は各自でリサーチしてみてください。

結果

日時 Total Reading Listening Speaking Writing
2020/12 66 19 14 16 17
2021/6 80 22 21 20 17
2022/2 (Unofficial) 103 29 25 21 28
2022/3 100 30 26 21 23

と、いうことで。とりあえず念願の3桁台に乗ることができました！ただ結果が出るまでは110点も夢じゃないと思っていたので、ギリギリな点数だったのは正直ショックです。

まず嬉しかったのはReading満点！ReadingとListeningの結果は試験終了後すぐにわかるのですが、めちゃくちゃ嬉しくて帰り道ずっとニコニコしてました。練習でも満点は確か1回しかとったことがなかったので、本当に嬉しかったです。(でも総合点を見ると、Readingで満点取れてなければ100点に乗らなかったわけで、そう考えると怖いね…)

Listeningも思ったほど悪くなく、2月の模試よりも1点上がりました。こちらも練習では満点とか1ミスとかでできたときもあったので、欲を言えばもっと欲しい気もしますが、まあ十分です。

ただ、SpeakingとWritingは意外と点が出ませんでした…。特にWritingはTPOで28点出せていたのに本番は23点で、なぜ…?? となっています。余裕があればもう1回受けようかなぁ。Speakingも対策した割には上がらず。これはもう少し研究が必要かもしれませんね。

ということで、一昨年から今年にかけてのTOEFL iBTの話でした。

なぜTOEFL受けてるの？なぜ高得点を目指してるの？という話ですが、ちゃんと理由があります。今後はその目的達成に向けた第2ステップに向けて、いろいろ進めていこうと思います。

ここまで読んでくださりありがとうございました！

P≠NP問題とはなにか？【Wathematica Advent Calendar 2021】

数学

Wathematica Advent Calendarの12/7の記事です。

現代の数学はとても広範で深遠な発展を遂げています。しかしそれでも、いまだに証明・反証がなされていない「未解決問題」というものが数多くあります。

例えばかの有名なフェルマーの最終定理はつい25年前までは未解決問題でした。つまり、それまではフェルマーの最終定理が本当に成り立つのか、あるいは成り立たないような反例があるのか、誰もわからなかった。

ABC予想の解決もそうですね。京大の望月教授が解決したということで、去年か一昨年に大きな話題になったと思います。あの命題も望月教授の論文が受理されるまでは「未解決問題」であり、だから名前も「ABC"予想"」だったわけです。

この2つの例はすでに解決されてしまった例ですが、今回紹介するのはいまだに未解決であるうちの一つの問題、「P≠NP問題」です。

P≠NP問題とは?

P≠NP問題とは、簡単に言うとアルゴリズムの「計算量」に関する問題です。計算量と聞いてぱっと来ない人も多いと思うので、例を挙げておきましょう。

計算量について

<例>(足し算問題) 正の整数nに対して、1+2+\cdots+nを求めたい。この計算はどれくらいの計算量で行えるか？

(「1回の計算」とは、2つの数の加減乗除を行うことを指すものとする)

この問題文に書いてある計算を実行する方法はいろいろあります。一番単純な方法としては、

(Step 1) 1+2を計算する

(Step 2) 上で求めた数に3を足す

(Step 3) 上で求めた数に4を足す

…………

(Step n-1) 上で求めた数にnを足す

という方法がありますね。この場合の計算回数は (n-1)回 となります。

つまり、この問題は高々(n-1)回の計算を行えば解ける、ということです。このとき、この問題は計算量O(n-1)で解けるといいます。

n \rightarrow \inftyとしたときはnもn-1も発散速度は変わらないので、通常はO(n-1)ではなくO(n)と書くことが多いです。ちなみにO(n)は「おーだーえぬ」と読みます。

実はこの「足し算問題」は、ほかの解き方をすることもできます。数学Bあたりで習うと思いますが、

1+2+\cdots+n=\frac{n(n+1)}{2}

という公式がありましたね。これを使うと、次のように計算ができます:

(Step 1) n+1 を計算

(Step 2) n \times (n+1) を計算

(Step 3) (1)で求めた数を2で割る

なんと、3回で計算が終わってしまいます！ここで大事なのは「どんなnに対しても」3回で計算が終わるということです。と、いうことでこの問題は計算量O(3)で解けます。3も1も発散速度が変わらない(発散しない)ので、通常は O(1)と書きます。

ちなみに、実際はどんなnに対しても計算時間が同じ、というわけではありません。人間にとってはもちろん、コンピューターにとっても、1+2+\cdots+100000000000000を計算する方が 1+2+3を計算するよりも(機械はほんの少しだけ)大変です。

その理由は「『1回の計算』とは、2つの数の加減乗除を行うことを指すものとする」というところにあります。でも実際は、例えば5桁の数同士を足し算するときはまず一の位同士を足して、次に十の位を足して、...、というように5回の計算をしていますよね。このように「桁数」を考慮していないので、一見奇妙な結果が生まれるわけです。でも大まかなイメージはつかめていただけたかと。

P問題

ここからはいろいろな「計算問題」を分類していきます。

あるkがあり、計算量 O(n^{k})で解けるような問題を「多項式時間で解ける」問題、または「P問題」といいます。例えば、さっきの足し算問題はP問題です。なぜかというと、方法1を使えばこの問題は O(n)=O(n^{1})で解けるからです。ちなみにPは英語でPolynomial(多項式)のことです。

もしある問題が計算量 O(n^{999})では解けなくても、計算量 O(n^{1000})で解けたらP問題になります。

多項式時間での計算は、(例えそれがO(n^{1000})であっても)「速い」計算とみなされます。では逆に「遅い」計算とは何か？例えば計算量が O(n!)や O(2^{n})必要な計算です。 n=1,2,3,...といった小さい数では n!や 2^{n}は n^{1000}に比べて圧倒的に小さな数ですが、nが大きくなっていくと最終的には前者の方がずっと大きな数になってしまいます。(これは、 \frac{2^{n}}{n^{1000}} \rightarrow \infty \, (n \rightarrow \infty)であることからわかります。

NP問題

一方、「答えが正しいかを多項式時間で確認できる」問題を「NP問題」といいます。NP問題であるが、P問題であるかはわからないものの例を挙げてみましょう。わかりやすいように設定を変えて、Twitterを使って考えてみます。

<例>(クリーク発見問題) Twitter上のn個のアカウントが与えられる。 k \leq nとする。 このとき、与えられたアカウントの中で、次の条件を満たすk個のアカウントの集合を発見できるか？:

「そのk個のアカウントのうち、任意の2つはFF(相互フォロー)の関係にある」

　　

この問題は、答えを見つけるのは難しいですが、もし答えが与えられたら確認作業は容易に( O(n^{2})で)できます。(理由は読者への演習問題としよう)

つまり、答えを高速に計算できるかはわからないのでP問題かの判断はまだできませんが、答えの検証は高速に行えるのでNP問題であるといえます。

ある問題がP問題なら、それは必ずNP問題にもなります。なぜなら、P問題で多項式時間で計算した答えは必ず正しいからです。なので、「まず多項式時間で答えを計算する」「次にそれが与えられたものと一致するかを調べる」ということを行えばいいわけです。

P≠NP問題

ではここで本題に入りましょう。P≠NP問題とはすなわち、

「NP問題ではあるけど、P問題ではないような計算問題はあるか？」

という問題です。言い換えると、

「答えを言われればすぐに納得できるけど、自分で答えを出すのにはとても時間がかかるような問題はあるか？」

ということです。ただし「とても時間がかかる」というのは直観と必ずしも合致しないので注意してください。

P≠NP問題の行く先

P≠NP問題の行く先として考えられる可能性は3つあります。それは、

・P=NP、つまりすべてのNP問題はP問題である

・P≠NP、つまりNP問題だがP問題ではないものがある。

・決定不能。すなわち、「そもそもP≠NP問題に対する証明・反証が存在しない」ことが証明できる。

というものです。

多くの数学者はP≠NPだろうと予測しています。P=NPなら、今までできないと思われていた多くのことができるようになり、様々な分野で大きなブレイクスルーが起きるかもしれません。

「証明・反証が存在しない」というのは少し理解が難しいかもしれません。ゲーデルの不完全性定理を知っている人はピンとくるでしょう。

ミレニアム懸賞問題

数学の世界にはこのように、解決が難しい問題がたくさんあります。P≠NP問題はその中でもトップレベルに難しいもので、アメリカのクレイ研究所によって「ミレニアム懸賞問題」に指定されています。これを解くと、なんと100万ドルをもらえるそうです！解決する自信のある方、富豪になりたい方は是非どうぞ！

ちなみにミレニアム懸賞問題は7つありますが、そのうちの1つ(ポアンカレ予想)だけが解決されており、P≠NPを含む残りの6つは未解決だそうです。

おまけ

Wathematicaが100万ドルを獲得する日もそう遠くないのかも...??

f:id:i7_yoc:20211205214644p:plain

参考資料

[1] 数学セミナー2013年12月号「P≠NP予想最前線」日本評論社, 2013

[2] Michael A. Nielsen, Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2010

[3] "P vs NP problem" https://www.claymath.org/millennium-problems/p-vs-np-problem Clay Mathematics Institute, 2021/12/06閲覧

TOEFL

その他

お久しぶりです。

久しぶりに何か書こうと思って、最近やっているTOEFLのことを少し書こうかなと思いました。

 

・2020/12時点のスコア

R: 19, L: 14, S: 16, W: 17   Total: 66

初回の点数です。よくはないですね。Lが特に。

で、何が敗因だったかというと、

・そもそも初回なのでどのようなものかをよく把握していなかった

・Sの話し方、Wの書き方の練習をちゃんとやっていなかったので、特に構成が悲惨だったのだと思う(よく覚えていない)

・Lに関してもメモを取る練習をあまりしていなかった

・教材代をケチって古本屋で買いあさっていたので、あまり傾向があっていなかった。特にLのpassageの長さに本番びっくりした覚えがある

 

という感じでしょうか。要は一言で言えば「精進不足」でしたね。

ということで、2回目に向けて、

 

・ListeningとSpeakingを重点的に強化。市販の教材(確かLはトフルゼミナール、SはZ会)をまずは1周して要領をつかむ。

・・・正直教材はどこのでもいい気がしてます。旺文社、Z会、トフルゼミナールの中から本屋で立ち読みして一番良さそうなのを買っただけですので。

 

・特にLに関しては「どう答えにつなげるか」よりもまず「何を言っているのか認識する」段階から始めることにした。

・・・これに関してはシャドーイングの練習がかなり有効だったと思います。この教材で勉強しました。といっても最初の1/3くらいしかやってないんですが、それでもだいぶリスニング能力が改善したような気がします。

www.kadokawa.co.jp

・Rに関しては、ぼちぼち問題を解きつつ本業の数学の方で洋書を読み始めていたのでそれでカバーできるのでは？と思っていた(甘い)。

・Wまで手が回らなかった(めちゃめちゃ甘い)

ということで今振り返るとすごくぬるい対策しかしてこなかったわけです。そして2回目(2021/6)の結果は、

R: 22, L: 21, S: 20, W: 17   Total: 80

ということで、とりあえずの目標にしていた80点にはぎりぎり届きました！やはり集中的に対策したLとSはしっかり伸びてくれました。その一方でほぼ何もしてないWに関しては点数もそのまま…

あと、2回目はHome Edition(=自宅受験)で受けたのですがこれが結構めんどくさい。始まる前の試験官とのコミュニケーションがうまくいかなかったり、休憩時間になっても試験官からの指示が全くなかったり、挙句の果てには終わって試験官に呼び掛けても何も返事がない。退出してしまったら後日ETSから「ホワイトボードを消してるのが確認できなかった。今回はスコア出すけど気をつけろよ(意訳)」的なお叱りメールが届いたりしました。次からは会場受験かなぁ。

 

で、2回目の反省ですが、

・Writingの対策という概念がなかった(????)

・そろそろちゃんと語彙を身につけたほうがよさそう。練習しているとき、選択肢の単語の意味を間違えるミスがそこそこあった。

この2点が大きいですね。

 

さて、次の申し込みもすでに済ませてあります。それまでにすべきことは、

・Writingの対策…すでに問題集を買って、Integrated Taskは大体要領を得たと思います。あとはTPOをひたすら回すのとIndependent Taskの練習

・6月に受けて以降、夏休みの間TOEFLと疎遠な生活をしていたせいでRとSの能力がだいぶ落ちているのでリハビリ。

・Rは引き続き問題演習と洋書の読書で対策。ちゃんとPrefaceなども(できる限り)自力で読むようにする

・単語はやっと王道の3800を購入。とりあえず~80までの単語は1周したが、かなり知らない語が多かった。でもその単語力でも実際に80点取れているんだから、単語ちゃんとやればもっともっと伸びるのでは？

 

ということで、今後も頑張ります！

一つの大きな機会に向けて練習していく、というのは情報オリンピックやパソコン甲子園なんかをやっていた頃を思い出しますね。自分でいうことではないですが、あの時(自分なりには)結構努力してそれなりの成果も残せたので、それが今も自信につながっている気がします。

もうすぐ二十歳の節目なのでもう一つくらい記事を書きたいですね。それでは！