「無限サイズの三次元イジング模型の厳密解は求められない」を厳密に定義するとしたらどうなるか?
「五次方程式の解の公式は存在しない」定理は有名だけれど、これは有限回の四則演算とべき根の組み合わせで表現できないという定理。同じように使える演算を決めれば定義はできる。しかし何が適切なのかよく分からない。無限級数と有限回の積分くらいに収まっていれば解けたといっていいと思うけれど、では初等関数の入った方程式の解として求められたらそれはダメなの? 微分方程式の解としては? うーん。
計算論的には「任意精度で解を近似できるアルゴリズムが存在しない」でいいのかな。ぱらっと検索してみる限り、実数の計算可能性の定義はこれで良さそう。しかし N → ∞ で厳密解に収束する自明なアルゴリズム f(N) はすでにある。つまりこの定義で厳密解はすでに計算できていることになる (誤差が温度の関数になっているのが気になるけれど)。先ほど「無限級数でかけたら解けたといっていい」などと書いたけれど、これもしかして無限級数で書けているのでは。何らかの計算量の制限がほしい。誤差 ε に対して 1/ε の多項式時間とか。
有限サイズの場合を考えると、上の意味では明らかに計算可能だけれど、普通これを解けるとは言わない。厳密解が求められると言ったら、サイト数に対して定数時間で計算できるアルゴリズムを指すと思う。とはいえ多項式時間で計算できても十分すごいし、もう少し緩めて NP 完全なら「解けない」としていい気がする。
こういう実数の問題に対して具体的な議論ができる計算論の道具はあるんだろうか。