こんにちは。新卒入社１年目の笹木です。
私は大学院で3年ほど数学の研究をしたのち、学部で学んだITの世界に戻ることにしました。
今回のブログでは自己紹介も兼ねて、IT系学部出身の私が大学院で数学を学ぶきっかけになったものについてお話したいと思います。
コンピュータが計算できないもの
突然ですが、こんなことを考えたことがあるでしょうか。
「コンピュータで計算できないものは存在するか？」と。
近年のコンピュータの計算能力の進化はすさまじいものです。
AIやディープラーニングなどによって様々な革新的な技術が実現され、
今やコンピュータにできないことなんてあるのか？というくらいまでになってきています。
しかし、数学的に考えてコンピュータに計算できないものは存在します。
Alan Turing は現代のコンピューターの原型となる数学的計算モデルである Turing Machineを
発表した論文の中で、これについて言及しています。歴史上はじめて証明された計算不可能問題、いわゆる停止問題です。
プログラミングをしたことがない人でもPCを触っていれば感覚として伝わるかと思いますが、
コンピュータプログラムは計算が終了するか、永遠に終わらないかのどちらかしかありません。
計算が永遠に終わらないというのは、フリーズ状態のような場合を思い浮かべてください。
フリーズするかどうかわからないのは不便なので、コンピュータプログラムの計算が終了するかどうかを判定するプログラムがあれば便利そうです。
停止判定プログラムがつくれるか
（※ここから少し数学チックな話になります。難しければ読み飛ばしていただいて構いません。)
ここでをプログラム
に
を入力したとき、計算が終了するなら
, 終了しないなら
を返すプログラムを表すものとします。
こんなプログラムがあったらいいですよね。あると仮定してみましょう。（ここで入力はバイナリとみなして、プログラムも入力できることにします。）
こんどはを
が
を出力したら計算が終了せず、
を出力したら
を出力して計算を終了するプログラムを表すものとします。
（プログラムが存在すれば、if文やwhile文などを使ってこのようなプログラムは簡単に作れます）
さて、ここでを考えてみましょう。（このようなメタ的な形を対角化という場合があります）
① の計算が終了した場合
が
を出力しているはずですが、すると
の定義から
の計算は終了しないことになり矛盾。
② の計算が終了しない場合
が
を出力しているはずですが、すると
の定義から
の計算が終了することになり矛盾。
どちらの場合も矛盾がおきます。これはプログラムが存在すると仮定したためにおきた矛盾なので、結果的にこのようなプログラムは存在しないことがわかります。
あくまで数学的な話なので、現実的にこれがどういう意味をもっているかは別の話ですが、こんなことが簡単に証明できたりします。
私が数学を学び始めたきっかけ
私はIT系学部の授業の中でこれと出会いました。
計算理論という分野では、このようにコンピュータの計算を数学的に扱うことができます。
コンピュータが計算できない問題は、現実世界の中だけで考えると想像しづらいですが、数学的にはありふれています。
計算理論を使うとそれらの問題が「どの程度難しいか」であったり、計算できる問題も「どの程度複雑か」などもわかります。
「計算」という一見シンプルな概念を基準にした数学の世界の切り取り方に惹かれて、私は数学を学び始めました。
自分が普段扱うもの（今回の場合はコンピュータ）が一体どんなものなのかを知ることはとても大切です。
高校までに習うものだけでなく、私たちの生活の周りには意外な数学があふれています。
皆さんもぜひ勉強してみてはいかがでしょうか。
