「ビジービーバー関数Σ」について

質問

「ビジービーバー関数Σ」は発散する速度が急速なために、n＝1,2,3,4のとき、Σ(n)＝1,4,6,13になるのですが、Σ(6)は少なくとも1.29×10^865になるそうです。そこで疑問に思ったのが、この関数Σの計算過程です。一体どのようになっているのでしょうか。知っている方がいれば教えてください。(「Σ」の記号は、僕はあくまでガンマ関数などの「Γ」などと同類の記号だと思います。)

回答No.1

ojisan7 · ベストアンサー

計算可能理論の書籍を熟読されることをお薦めします。オートマトンやTuring machineについて詳しく説明されている和書も、いくつかあるようです。ご存じのように、Busy Beaver 関数は数式で表すことはできません。分かりやすい解説（厳密性には欠けますが）が以下のＵＲＬ（参考ＵＲＬ）にも掲載されていますので、参考にして下さい。また、次のＵＲＬも読んでみて下さい。

http://mathworld.wolfram.com/BusyBeaver.html

http://www.logique.jussieu.fr/~michel/tmi.html

ともかく、専門書を購入して、じっくり考えながら読まれることをお薦めします。

回答No.2

ojisan7

すみません。参考ＵＲＬが消えてしまいました。再度、お試し下さい。

参考URL：

http://www.ice.nuie.nagoya-u.ac.jp/~h003149b/lang/undecidable.html