ついでに440-441もコピー

440 ：通りすがり：2006/03/09(木) 18:27:05
●STEP0
比較的単純なマシンモデル（チューリングマシン）を定義することで、
どのような帰納的定義の関数よりも早く増大する関数、ビジービーバー関数が定義出来た。
ビジービーバー関数は「どのような帰納的定義の関数よりも早く増大する関数」の中ではほとんどＭＩＮの関数である。
BBに帰納的拡張をしていくことである程度大きくすることは可能。、
（BB^n(2)やBBのふぃっしゅ数的拡張など）

●STEP1
チューリングマシンにビジービーバーの値を返す動作を追加したマシンを考えてみる。
厳密にはたとえば、
各ステートの動作定義に１ビット加え、このビットが立っていたら
BB(テープ上のヘッド位置から右に続く１の数)個の１をヘッドの右側に書き込むという動作で良い。
このマシンｎステートでセット可能な１の数の最大をBB2(n)とすると、
この関数はビジービーバー関数に通常の多重帰納的定義を用いて拡張したどんな関数よりも早く増加する。
（BBのふぃっしゅ数的拡張もBB2に及ばない）

一般に、
『チューリングマシン＋関数f』のマシンｎステートで
セット可能な１の数の最大をBB｢f｣(n)とする。
BB｢f｣ は、fに通常の多重帰納的定義を用いて拡張したどんな関数よりも早く増加する。
BB｢恒等変換｣ = ビジービーバーであり、
BB｢ビジービーバー｣ が上の BB2 である。

BB｢f｣の｢｣の中に関数を入れることで新たな関数ができ、
帰納的定義の関数のように帰納的にBB｢f｣の定義が可能である。