07/09/13 20:35:35
計算可能な関数とは、>>260 のようなプログラムで書ける関数のこと。
ビジービーバー関数とは、プログラムn文字で作り出せる最大の数。（※）
だからプログラムで書けるどんな関数よりも増大度が大きい。
※実際はBBはチューリングマシンという非常に単純なマシンでの定義となる
ただ、
すべての値に対してBB(n)を返すプログラムがかけないというだけであって、
BB(10)やBB(100)を返すプログラムの存在を否定するものではない。
07/09/13 20:35:35
計算可能な関数とは、>>260 のようなプログラムで書ける関数のこと。
ビジービーバー関数とは、プログラムn文字で作り出せる最大の数。（※）
だからプログラムで書けるどんな関数よりも増大度が大きい。
※実際はBBはチューリングマシンという非常に単純なマシンでの定義となる
ただ、
すべての値に対してBB(n)を返すプログラムがかけないというだけであって、
BB(10)やBB(100)を返すプログラムの存在を否定するものではない。