07/04/06 23:12:40
停止問題を解くことが出来るマシンを考えればずっと大きな数を作ることが出来る。
あるチューリング完全マシンをMachine[0],
Macihne[0]のn命令のプログラムで表現可能な最大の数をM[0](n)とすると、
M[0](n) ≒ BB(n)
Machine[0] の停止問題を解く命令をhalt[1],
Machine[0] に halt[1] の命令を追加したマシンを Machine[1],
Macihne[1]のn命令のプログラムで表現可能な最大の数をM[1](n)とすると、
M[1](n) は 前スレ >>863 の mm(n) を大きく超える。
Machine[a]のｎ命令のプログラムで表現可能な最大の数をM[a](n)
Machine[a] の停止問題を解く命令をhalt[a+1]
Machine[a] に halt[a+1] の命令を追加したマシンを M[a+1]
としてM[a]を定義することが出来る。
halt[a] を 「b<a となるすべてのマシン Machine[b] の停止問題を解く命令」としても同じであり、
この定義にすると、a を順序集合に拡張できるようになる。
M[ω](n), M[ω^ω](n), M[Γ_0](n) などが定義できる。