【数学小話】人類には「ほとんど全ての数が"計算不可能"である」という事実。

数とは、もともとヒトが創り出した概念であり、計算することを生業なりわいとしていたはずです。その立場から、

という事実を俯瞰ふかんすると、「人類と計算機の限界」や「数と計算の乖離」を感じるのではないでしょうか？この、表現し難い"奇妙さ"を楽しみながら、その事実について詳しく見ていきましょう。

⠀（PR）

ザックリ理解向け

計算可能/不可能

計算不可能とは、手計算でも計算機でも、さらには近年大盛り上がりのAI（人工知能）や量子コンピュータでさえ、具体的な値を計算することが叶わないということを指します。↵⠀[1]

逆に計算が"できる"数を計算可能数（Computable number）と呼び、「コンピュータによって好きな精度の近似値を出力することが可能な数」を指します。計算可能数は全体から見てホンの一握り↵⠀[2]しか存在しませんが、幸いにも$0,1,\sqrt{2},\pi,e,\ldots$といった皆さんが想起する基本的な数は計算可能数に属します。↵⠀[b]

物事はできるかできないかの二者択一なので、数は計算可能数であるか、はたまた計算不可能数であるかのどちらかしかありません。そして、

というのが、先ほど述べた事実の主張です。

規模感

計算"できない"ものが圧倒的大多数ですが、数全体から見るとどの程度なものなのでしょう？

その規模感を簡単に例えるのであれば、宇宙と地球との関係性に近しいです。つまりは、宇宙全体を数全体と考えたとき、地球が計算可能数で、その他宇宙空間が計算不可能数だということです。↵⠀[3]

言葉だけではどうしても伝わりにくいものがあるので、ココで動画を紹介させて下さい。以下の動画では、地球を出発点として太陽系ー銀河系ー銀河団ー超銀河団ー観測可能宇宙と視野が広がり、宇宙全体における地球の規模感が分かりやすく表現されています：

また、地球がヒトにとって有用的であるように、計算可能数は$0,1,\sqrt{2},\pi,e,\ldots$といった有用的な数です。加えて、宇宙空間からみた地球が青くて、丸くて、美しく感じるように、計算可能数の全貌を見渡すには計算不可能数の存在は不可欠です。それぞれにはそれぞれの特徴があるというだけで、存在の優劣はないということを付け加えておきます。

ロジック

一般的に、$0,1,2,3,4,…$と数は無数に存在します。その一部分である計算可能数や計算不可能数も無数に存在します。ここでは、

というロジックについて解説します。

「計算」の背景には必ず「プログラム」が存在します。それらプログラムは"文字"によって構成されています。ここでは文字をアルファベット$a,b,c,d,e$に限定して考え、それらを並べることで$0,1,\sqrt{2},\pi,e,\ldots$といった数を出力するプログラムが構築できると考えます。

ここで第１ステップとして、取り得うる文字の並びを以下のように整列させます。このとき、パターンは無数にあることに留意して下さい：

次に第２ステップとして、意味を成さないプログラムを除外します↵⠀[4]：

さらに第３ステップとして、同じ数を出力するプログラム同士を１つにまとめて考えます↵⠀[4]：

最終ステップとして、若い方から順に$0,1,2,3,\ldots$と番号付けします：

上記の手順により、自然数・プログラム・計算可能数のそれぞれが被りなく対応していることが見て取れるでしょう。↵⠀[5]「計算」の背景には「プログラム」があり、その背景には「自然数」が対応しているという状況です：

ここで、

という"数"を知らない小学生でも理解できるロジックを用いると、自然数全体と計算可能数全体が１対１対応をしているため、これらは同程度の個数↵⠀[6]であるという結論が得られます。

このロジックをベースに議論を重ねていくとやがて、

という結論が得られます。↵⠀[7]

⠀（PR）

計算不可能数の例

圧倒的大多数の計算不可能数ですが、その実体を表現することは非常に難しいとされています。それもそのはずで、「計算できないこと」が計算不可能数たらしめる所以ゆえんであるため、具体的な数値を表現できてしまえばそれは計算不可能数ではないです。

しかし、具体的ではないにせよ計算不可能数の例は２つほど知られています。

１つ目の例は、先ほどの「自然数と対応付けた計算可能数」を利用して人為的に生成する例です。

計算可能数の小数部を抜き出し、その対角線に着目します。登場する数字を$0\to1,1\to2,\ldots,8\to9,9\to0$と置換して得られた新たな数（例：$0.5246\ldots$）は、どの計算可能数とも異なり、表の中に存在しません。↵⠀[8]

例示された数$0.5246\ldots$を計算してみようとしても、「無限に数を書き連ねた表」をプログラム内に記述することは不可能であるため↵⠀[9]、やはり計算不可能数の一例であったことが分かります。

２つ目の例は、「（ランダムに選ばれた）プログラムの停止確率」を表す定数$\Omega$↵⠀[10]です。

というような自己言及的な文章は、意味が破綻してしまうことが往々にしてあります。実際に上記文章であれば、

• 文章が「正しい」と仮定
  →「嘘」であることが「正しい」ので文章は「嘘」
  →「正しい」のに「嘘」であるため矛盾

• 文章が「嘘」と仮定
  →「嘘」というのが「嘘」であるため文章は「正しい」
  →「嘘」なのに「正しい」ため矛盾

と意味が破綻しています。

これと同様なことを「計算」の背景にある「プログラム」においても考えることができ、それが「プログラムの停止確率」です。

プログラムの停止確率$\Omega$は原理的に$0\le\Omega\le1$の範囲で存在しますが、自己言及的な定数であるため、プログラムを組むことができず↵⠀[11]、計算不可能数の一例だということが分かります。

まとめ

• 計算可能性は「プログラムの構築可能性」であり、$0,1,\sqrt{2},\pi,e,\ldots$などの計算可能数は数全体からするとホンの一握りの存在である。

• 存在度合いの論拠は「１つ１つを対応させ、余った方を多い方、余らなければ同数と考える」ところにあり、数全体は計算可能数全体と対応付けて余った方、すなわち多い方である。

• ほとんどの数が計算できないが、計算できないが故に知られている計算不可能数の例は、数えるほどしかない。

📚この記事を読んだ方はこんな記事も読んでいます

脚注

注釈

[1] ^ 量子コンピュータも古典的コンピュータも、この議論における本質的な違いはない。↵⠀[a]

[2] ^ 計算可能数全体の集合が可算無限であり、ルベーグ測度がゼロであるという意味での表現である。

[3] ^ 非可算無限集合である数全体を有限である宇宙に例えている点など、多くの点で数学的妥当性・必然性のない比喩表現を用いている。

[4] ^ プログラムの除外や同一視という工程により、残されたプログラムが有限個に収まってしまうケースも考えられる。しかしながら、任意の自然数が出力可能であることは自明であるため、上記の工程を経ても有限個に収まるようなことはない。

[5] ^ 日本の学校教育↵⠀[c]においてはゼロを自然数に含めない立場を取るが、ここではゼロを含める立場を取っている。

[6] ^ 濃度が等しいという意味である。

[7] ^ 本来は「ルベーグ測度がゼロである」という議論が必要であるため、厳密には不十分で雰囲気説明である。

[8] ^ このような論法をカントールの対角線論法という。実際は「小数表示は一意ではない（例：$1.000\ldots=0.999\ldots$）」という問題があるため、この手の議論は慎重に行うべきである。

[9] ^ 「無限個のリスト」という静的オブジェクトを実装することができないことは明らかであるが、"必要な精度に応じて動的に有限個のリストを作成する方法"はどうだろう？この方法においても実装することはできない。なぜならば、リストの生成過程のうち、「意味を成さないプログラムの除外」が停止性問題に直結するためである。意味を成さないプログラムには、「無限ループによって停止しないプログラム」も含まれ、これは決定不可能であることが証明されている。また、仮に問題なく除外できたとしても「同じ数を出力するプログラムの同一視」という工程が計算の困難さを招くため、やはり動的に生成することは叶わないであろう。

[10] ^ チャイティンの定数。$\displaystyle\Omega\coloneqq\sum_{p\in P}2^{-|p|}$と定義される符号化方式ごと固有の定数である。ここで、$P$は停止するプログラム全体の集合、$|p|$は停止するプログラム$p$をバイナリ表現（01表現）したときの桁数である。↵⠀[d]

[11] ^ 自己言及的な文章であれば必ず破綻するとは限らない。実際に「この文章は真実である。」という文章は破綻しない。破綻するか否かは個別で判断する必要があり、今回の停止確率における論拠は停止性問題にある。

出典

[a] ^ 講義 #20 まとめ：「計算」の研究，計算不可能性の研究｜「計算」の世界へ

[b] ^ 計算可能数#実数の代わりとして｜Wikipedia

[c] ^ 【数学編】中学校学習指導要領（平成29年告示）解説 ｜文部科学省

[d] ^ チャイティンが実装した停止確率Ωに関するコードの覚書｜中井悦司