WEBプログラマーインターンの挑戦｜実務で磨く制作スキルと成長【11/06】

こんにちは！社長室所属WEBプログラマーコースインターン生の小西光柊です。
いつもは業務関係の日記ばっかり書いているのでたまには数学徒らしくそれっぽい話をしてみようと思います。

【本日のテーマ】停止性問題

上記のテーマはプログラミング、数学の両方に深く関わりのあるものです。
プログラミングをやったことのある方であれば一度は何かミスがあって無限ループに陥ってしまったという経験があるのではないでしょうか、

そんな時にもし事前に100%の精度でそのプログラムが停止するかどうか判断できるプログラムがあった便利だと思いませんか？

この問題は実際そんな停止性判定プログラムは存在できるのだろうか、という問題です。

この内容のご覧の皆様、答えはどっちだと思いますか？

正解は

存在できない！です。

これがもし存在してしまった場合いろいろとアルゴリズムのルールに矛盾が生じてしまっておかしいじゃないか！

というような流れで数学的に証明ができてしまいます。

このプログラムにおける話題いったいどこに数学との関連性があるのかというとですね

この問題ゲーデルの不完全性定理と呼ばれる非常に重要な定理の証明の一端を担うようなものなんですね。

この定理自体は任意の命題が真か偽か判断できるとは限らないといったものです。

プログラムが停止するかどうか、命題が判断できるかどうか...どこか似ているような感じがしますよね。

こんな風に数学とプログラムには関わりの深い話が多くありますのでまた機会があれば書けたらと思います。

メンバー紹介

長期インターン生の活動日記