素数からアッカーマン関数、そしてウィランズの素数公式へ

昨日は、「存在する／しない」について考えていた。
数学で明確に定義できる概念は、「存在する」と言ってよいのかどうか、という話である。

最初の具体的な問いは、
n 番目の素数を返す関数である。これを仮にPr(n) と書く。
n という整数を入れれば、それに対応する素数を返す関数は、機能としてははっきりしている。だから数学的な抽象の世界では、こうした関数は存在すると言ってよさそうに思える。

ただし、ここで「存在する」と「実際に計算しやすい」は別である。
n 番目の素数は原理上は求められるが、
n が巨大になると現実的な計算はたいへん難しくなる。
定義できることと、手軽に求められることは同じではない。

次に思い浮かんだのが、アッカーマン関数である。
これは計算不能関数ではなく、定義もアルゴリズムも明確な、れっきとした計算可能関数である。
ただし、値の増え方があまりにも激烈なので、少し入力が大きくなるだけで実際には手に負えなくなる。

定義はこうである。
1. ac(0, m) = m + 1
2. ac(n, 0) = ac(n-1,1)
3. ac(n, m) = ac(n-1, ac(n, m-1))

これを使って、少しいじわるな問いを考えた。
k,l,m,n がそれぞれ314,159,265,358だとして　 (ってπの十進表記数字を3桁ずつ区切っただけ)

f(k,l,m,n)=ac(k,l)−ac(m,n)

この値は正か負か。また、性能がX(GFLOPS) のコンピュータで、その結果を何秒後に出せるか、それを見積もることは可能か。

GEMINI にこれを尋ねると、
f の符号は「正」とすぐ答えた。
しかし具体的な値も、計算時間の見積もりも「不可能」と返してきた。

この返答は、かなり象徴的である。
関数の定義は明確で、符号については構造からある程度の判断ができても、実際の値となると現実的計算の枠から完全にはみ出してしまう。
「定義できる」「計算可能である」「実際に扱える」は、それぞれ別の話なのだ。

ここからさらに Busy Beaver 問題のような、そもそも計算可能性そのものに限界がある話へ進めるのだが、これは面倒すぎるので今回は省略する。

そんなことを考えているうちに、そういえば
n 番目の素数を表す式をどこかで見た記憶がある、と思い出した。
それがウィランズの素数公式（Willans' formula）である。

一見すると、関数をひとつの閉じた式で書いてしまったようにも見える。
しかし、実用上の計算効率はよくないらしい。
素数を求めるという目的だけなら、古典的なエラトステネスのふるいの方がずっと有力だという。

閉じた式があることと、計算に使えることはまた別である。
このあたり、数学はときどき奇妙だ。

うーん、映画『メッセージ』に出てくる、変分原理的にものを考える宇宙人なら、ウィランズの公式よりもっと実用的な「素数の式」を持っているのかもしれない。