巨大数とビジービーバー

Takayuki Kihara @tri_iro

あっ、巨大数論が修正されるんだったら、ビジービーバー関数絡みのちょっと怪しい文章にコメントしておけばよかった。

p進大好きbot @non_archimedean

@tri_iro どこでしょうか？　あらゆる再帰的理論体系～のところでしょうか？（矛盾する再帰的理論体系を気にしていますか？）

Takayuki Kihara @tri_iro

@non_archimedean その辺りの記述も気になるのですが、保留中です。個人的には、 x 次ビジービーバーを何らかの意味で F[ω_xCK] に対応させることが可能というのは極めて疑わしいと思っています。

Takayuki Kihara @tri_iro

@non_archimedean というのも、2次ビジービーバーを神託にして計算可能な順序数の上限はω_1^{CK}ですし、どんな計算可能順序数 x を取ってきても x 次ビジービーバーを神託にして計算可能な順序数の上限はω_1^{CK}で、ω_1^{CK}は計算可能順序数の上限という程度ではない非常に強い閉包性をもつので

Takayuki Kihara @tri_iro

@non_archimedean つまり、どんな高次のビジービーバーを神託に使っても ω_2^{CK} すら計算できないのに、それが急増大階層の ω_x^{CK} レベルに行けるというのは信じ難い、というのがあります。

Takayuki Kihara @tri_iro

@non_archimedean ただ、具体的に ω_x^{CK} の基本列をどう取るか明示されていないのでなんとも言い難いのですが、 x 次ビジービーバーに相当するものは ω_x^{CK} ではなく ω_1^{CK}・x くらいが妥当かなと思うのですが、いかがでしょうか。

p進大好きbot @non_archimedean

@tri_iro ああ、そこですか。そこは計算可能理論の人がびっくりするジャーゴンだと思うのですが、FGHに出てくるω_x^CKの定義は通常の許容性（KPの充足性で定める再帰類似）ではなく、今の文脈に沿ったものを適宜考えているだけ、というものみたいです。

p進大好きbot @non_archimedean

@tri_iro 例えばビジービーバーがFGHでω_1^CKに対応する、というときも何らかの基本列が具体的に定義されてきっかり対応すると言っているのではなく、ビジービーバーそのものをFGHにおけるω_1^CKと表現しているとするようです。厳密な許容順序数との違いはたまに話題になります。

p進大好きbot @non_archimedean

@tri_iro ええ、実際そう書く流儀もあるようです。非再帰な順序数に対するFGHはかなりラフな扱いです。

rpakr @rpakr_googology

@tri_iro @non_archimedean 私もそこは疑わしいと思っています。

Takayuki Kihara @tri_iro

@non_archimedean ええ……なんかちゃんとした数学的定義のある用語をそこまで全然違う意味で使うのはやめてほしいですね……（その巨大数ジャーゴンだとω_x^CKの大きさがとんでもなく過小評価されているのでは）。せめてω_1^CK・x にして欲しいかなあという印象です。

p進大好きbot @non_archimedean

@tri_iro それは申し訳ないところですが、文化として「上からの評価は雑でよい」という原則があると思います。巨大さにしか興味がないので。

p進大好きbot @non_archimedean

@tri_iro あ、念のための補足ですが、数学用語としてのω_x^CKの大きさは多分誰も過小評価していません。別の定義ないし記法を導入しているだけです。

Takayuki Kihara @tri_iro

@non_archimedean 上からの評価は雑でよいかもしれませんが、ω_x^CKというジャーゴンが都合が良いのはビジービーバー辺りの小さい関数くらいで、もっと大きい一般の関数を考える際には普通の数学的用語と整合性が取れていた方が都合がよくないでしょうか？

p進大好きbot @non_archimedean

@tri_iro 計算不可能関数でFGHっぽい評価ができるのはせいぜいビジービーバー＋神託周りだけの非常に小さい関数なので、本気の計算不可能関数の評価に順序数が使えないんですよね。なので整合性はあまり気にされないと思います。 逆に計算可能関数で許容順序数を使う際はきっちり正しい定義を使います。

Takayuki Kihara @tri_iro

@non_archimedean 無限時間レジスターマシン（無限時間チューリングマシンより遥かに弱い）に対するビジービーバー辺りならFGHっぽい評価はできそうですが、無限時間RM周辺は許容順序数との対応が明確にわかっているので、その周辺を考えると，普通の許容順序数の用語と整合性が取れてた方が便利かなと思います

p進大好きbot @non_archimedean

@tri_iro そういうのがあるんですね。知らなかったです。計算可能関数の時はちゃんと整合的な定義を使うので、そういうのを考える時は整合的なのを使うんでしょうね。ビジービーバーをFGHっぽく書くのは単なるキャッチーな表記で、その裏に拡張のための目的とかは無さそうですからね。。

p進大好きbot @non_archimedean

@tri_iro ちなみに予見としてはそれに対応するビジービーバー関数はどれくらいの大きさになりそうでしょうか？

Takayuki Kihara @tri_iro

@non_archimedean ITRMビジービーバーをどう定義するかによりますが、nレジスターのITRMの計算能力が（普通の許容順序数の意味で）L_{ω_n^CK}の中の関数を全部計算できるくらいなので、ちょうどそれら全部より急増大する程度になると思います

rpakr @rpakr_googology

@non_archimedean @tri_iro 私も、2次ビジービーバーがω_2^CKだと主張する人に、f_{ω_1^CK×2}(x)を計算できるチューリングマシンの例を出してくださいと質問したことがありましたが、具体的なチューチングマシンは出されませんでした。

Takayuki Kihara @tri_iro

@rpakr_googology @non_archimedean 急増加関数の記法を厳密な意味で受け取るなら、どんなω_1^CKの基本列を取ってきても、f_{ω_1^CK×2} はビジービーバーを使っても計算不可能でしょうね。まあ厳密にはそもそも巨大数wikiにあるω_1^CKの基本列では、 f_{ω_1^CK}の時点でビジービーバーと完全に異なる振る舞いをするとは思いますが…

ふぃっしゅっしゅ 🐟🐠 @kyodaisuu

Gwiki の order-x busy beaver function がFGHで f_ω^CKx(n) という記述の履歴を調査した。 Ikosarakt1 さんが2013年1月30日に追加して googology.wikia.com/index.php?titl… 同じくIkosarakt1 さんが2015年2月11日に削除 googology.wikia.com/index.php?titl…