巨大数とビジービーバー

Takayuki Kihara @tri_iro

@kyodaisuu そこのTalkを見る限りでは、α次ビジービーバー程度でω_1^CK以上の順序数を計算できると勘違いしてるような発言がありますね…。

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

@tri_iro ここに ω_1^CKの基本列を作る方法が書かれていて googology.wikia.com/wiki/Church-Kl… それをFGHに適用することでF[ω_1^CK]を作ることができるのであれば FGHの定義からF[ω_1^CK+1]を作ることもできると考えてしまったのかもしれません。 計算不可能関数の世界は直感通りにはいかないので危険ですね…。

Takayuki Kihara @tri_iro

@kyodaisuu そこに書いてあるω_1^CKの基本列の複雑さが、そもそも任意の計算可能順序数xに対するx次ビジービーバーの複雑さを（計算不可能性の意味で）超えてるんですよね

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

@tri_iro そういうことでしたか。ありがとうございます。

rpakr @rpakr_googology

@kyodaisuu @tri_iro f_{ω_1^CK+1}(n)=f^n_{ω_1^CK}(n)ではないということですか？

Takayuki Kihara @tri_iro

@rpakr_googology @kyodaisuu f_{ω_1^CK+1}自体はそれでいいと思います。f_{ω_1^CK}が厳密にはどれくらいの急増大度になっているかが謎なだけであって

rpakr @rpakr_googology

@tri_iro @kyodaisuu f_{ω_1^CK}(n)≒BB(n)ではないのですか。

Takayuki Kihara @tri_iro

@rpakr_googology @kyodaisuu もちろん ω_1^CK の基本列の取り方によります。個人的には、厳密な意味では、 f_{ω_1^CK}(n)≒BB(n) となるような ω_1^CK の自然な基本列があるかどうかという点も疑っています。

rpakr @rpakr_googology

@tri_iro @kyodaisuu nは自然数とします。 「ω_1^CK[n]を、f_α(n)<BB(n)を満たす最大の順序数αとする。」とするとどうですか。

Takayuki Kihara @tri_iro

@rpakr_googology @kyodaisuu 順序数は最小は取れても最大は取れないので、もう少し工夫する必要がありますね。まあそこは BB(n)<f_α(n) を満たす最小の α に変えればいいと思います。ただ、これはどんな関数 g に対しても、f_{ω_1^CK} が g と同じくらいになるような ω_1^CK の基本列を持ってこれる、というだけのことなので……

Takayuki Kihara @tri_iro

@rpakr_googology @kyodaisuu その方法を使ってしまうと、ωの基本列として、「 ω[n] を BB(n) < f_m(n) を満たす最小の数 m とする」という感じに取ってきてしまうのと、ほとんど同じ理屈ですよね

Takayuki Kihara @tri_iro

@non_archimedean 保留にしていた、この再帰的理論体系〜の方なんですが、p進さんに聞くのは相手が違うかもしれませんが、矛盾する理論とか以前に、この文章をどういう意味で解釈されてます？

p進大好きbot @non_archimedean

@tri_iro 算術（QとかPRAとかお好みのもの）を含むeffectively axiomisable formal theory Tであってω無矛盾性がメタに強く信じられているものに対して、算術で定義可能な計算可能関数fであってT上可証全域かつ標準自然数を標準自然数に移し標準自然数回で停止するものである時、fの各標準自然数入力での停止性

p進大好きbot @non_archimedean

@tri_iro が算術で証明可能になるため、結果的にZFCでもその入力での停止性が証明可能であることがメタ証明可能になり、従ってそういうfはZFC上可証全域でなくてもビジービーバー関数で上から抑えられる、という感じのふわっとした解釈をしています。

p進大好きbot @non_archimedean

@tri_iro （算術で定義可能としているので、標準自然数を標準自然数に移し、の部分は蛇足でした）

Takayuki Kihara @tri_iro

@non_archimedean ご丁寧にありがとうございます。実際に書かれている内容よりだいぶ行間を埋められてますね。私はまた若干違う感じに読み取っていたんですが、ちょっと今日は夜も遅いので、明日あらためて返事します。

Takayuki Kihara @tri_iro

@non_archimedean あらゆる再帰的理論体系～の部分だけだと色々と解釈が可能ですが、その前の数行を読む限り、ビジービーバー関数の全域性が証明できないという、字面をそのまま解釈すれば正しくない主張を元に、証明能力を超えてると主張してるのかなと私は解釈しました。

Takayuki Kihara @tri_iro

@non_archimedean この辺りの文章は、いかなる再帰的理論でもビジービーバー関数の全域性を証明できない、全域性を再帰的な理論では証明できない、等々と何度も繰り返されていて、これはどういう意味のつもりで書いているのかなというが非常に気になっている点です。

p進大好きbot @non_archimedean

@tri_iro あー。その部分は『いかなる（無矛盾な）再帰的理論においても「ある可証全域計算可能関数fが存在して、fとビジービーバー関数が等しい」という文が証明できない』と受け取ってしまいましたが、字面のまま読むとビジービーバー関数自体が可証全域でないみたいですね。文脈で判断しちゃってました。

p進大好きbot @non_archimedean

@tri_iro 関数絡みで証明可能性の話は基本的に計算可能関数の全域性に関してしか基本的に扱わないことが多い（そして可証全域性は巨大基数公理と合わせてよく扱う）ので、多分そういうことを書きたかったのだと思いますが、ここだけ見ると確かに「ん？」となるかもしれませんね。

Takayuki Kihara @tri_iro

@non_archimedean その流れであれば、あの辺の文章について、p進さんの言うような意味で解釈できないこともないと思いますが、やはり字面だけ見ると正しくない文章なので、できればもう少し文章を修正してほしいところです。

p進大好きbot @non_archimedean

@tri_iro 今回の修正を逃してしまったのは痛かったですね。。巨大数界隈では関数と言ったら暗黙に計算可能なことを念頭に置くことが多く（高校生以下の層が厚いのか集合論を知らずに初等的算術のみ知っている層が多いためだと思います）、「ビジービーバー関数は定義できない」みたいな

p進大好きbot @non_archimedean

@tri_iro 言われ方をすることがちょくちょくあるんですよね。「計算不可能巨大数は計算できないから定義できてないと思う」みたいな。そんなこんなで計算不可能関数への言明は表現の仕方が結構界隈独特なのも一因かもしれませんね。