9 - 一般名無し質問者 2022/02/04(金) 01:02:36 ID:zHeuCXX30
計算可能性理論の話題が出ているので、せっかくだから計算可能でない関数の例を紹介します。
貴職らはコンピュータがあるばっかりにインターネット上で自分語りをして破滅した高校生を知っているから、コンピュータがあればあらゆることが実現できてしまうと思っているかもしれませんが、実はコンピュータには絶対解けない問題があることが知られています。
具体的には、コンピュータのプログラムが計算を完了して停止するかどうかを判定するプログラムは書けないことがわかっています。大ざっぱにいうと、無限ループが起きるかどうかはやってみないとわからない（ことがある）ということです。
証明は知っていればここに書ける程度には簡潔です。背理法で示します。
このようなプログラムHが存在するとしましょう。つまりHはそれ自身の入力としてプログラムPとPに対する入力Iを受け取り、PにIを入力として与えた時に停止するならYes、停止しないならNoを返すプログラムです。この計算結果をH(P, I)と書くことにします。
ここでプログラムAを、入力としてXを受け取ったときH(X, X)=YesならばAは意図的に無限ループを起こし（つまり停止しない）、H(X, X)=Noならば適当な値を返して停止するものとします。
このとき、
[1] H(A, A)=Yesとすると、Hの定義からA(A)は停止するが、Aの定義からA(A)は意図的な無限ループを起こすはずであり矛盾します。
[2] H(A, A)=Noとすると、Hの定義からA(A)は停止しないが、Aの定義からA(A)適当な値を返して停止するはずでありやはり矛盾します。
以上からH(A, A)としてあり得る値が存在しないので、最初に仮定したHの存在が誤りであることが示されました。
コンピュータの話をしていたはずなのに突然数学の証明が出てきて驚かれた人もいるかもしれませんが、これが理論計算機科学と呼ばれる分野の特徴でもあります。実際、理論計算機科学の研究者は大学では数学科に所属していたりします。