07/09/18 21:22:54
>>424
手段を問わないなら、
int を無限長整数としたC++言語で、
int function(int a);
という関数を作る。
10000文字以内でできるfunctionのうち増加度が最大のものの１個を考えれば、
この関数は計算可能だが増大度が非常に大きい関数となる。
関数 f と g は、
ある整数aが存在し、b>a となる全ての整数b に対し f(b) > g(b) が成り立った場合に
f > g とする。
上記の関数 f のうち、g > f となる関数 gが存在しないものを、増加度が最大であるとする。
増加度が最大のうちの１個の選び方は、
プログラムの前方からの比較で小さいものを選ぶ。
μ再帰関数でも同様の関数が作れる。
定義の中に基本関数が10000回以内出現するようなμ再帰関数の中で
増大度の最大のものを１個をえらぶ。
これも増大度の非常に大きい計算可能な関数となる。