巨大数とビジービーバー

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

@tri_iro @non_archimedean Gwiki では、計算可能関数の強さが「どの理論で全域性が証明不可能か」ということで段階分けされています。 googology.wikia.com/wiki/List_of_g… そのことから再帰理論で全域証明可能な関数は計算可能関数になるのではないかと思い込んでしまいました。再帰関数と計算可能関数が同じであるという記述を見たことも

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

@tri_iro @non_archimedean 混乱の元になっていたように思います。 いろいろと指摘をいただいていますので、2刷を出したばかりではありますが、3刷の発行を検討する必要もありそうです。あやしい記述をばっさりと削るか、しっかりと理解して書き直すか、いずれにしても（特に後者であれば）時間はかかりそうです。

Takayuki Kihara @tri_iro

@non_archimedean ただやっぱりそもそも計算不可能関数をFGHを使って測るのは微妙そうで、普通に巨大計算不可能関数をwell-definedに作っていく方向性であれば、FGHよりもJensenの微細構造理論の意味でのマスターコードと対応付けるのが自然かなと思うんですよね

Takayuki Kihara @tri_iro

@non_archimedean あ、マスターコードというかJ-階層のランクで対応づける感じという意味でした。そうすると、ビジービーバーに対応する順序数が1 （x次ビジービーバーに対応する順序数がx）になってしまい、FGHでの話と順序数がずれるのと、Lに属すという意味で構成可能な計算不可能関数しか測れないのが難点ですが…

p進大好きbot @non_archimedean

@tri_iro 全く存じ上げない話でした。巨大関数をFGHで評価するのは主に計算可能関数で、ビジービーバー関数をFGHっぽく書くのは計算可能関数しか知らない人のための配慮（イメージさせやすくする）っぽいもので、計算不可能関数の正確な評価に興味がある人が多分ほとんどいないんですよね。

p進大好きbot @non_archimedean

@tri_iro しかも大きさと分かりやすさを重視する界隈なので、TMとITTMの間の強さのものの評価自体もあまり重視されないと思うので、そういう厳密な対応に光が当たりにくいんじゃないかと思います。ITTM自体も多分計算不可能界隈ではほぼTMと同じ程度の弱いものという扱いだと思いますので、話題も少ないです。

p進大好きbot @non_archimedean

@tri_iro 特にLに入るとなるとかなり注目が浴びにくいと思います。界隈は公理を軽視している（ZFCでできない議論ですら公理を明示しない）ので、Lに入りようのない計算不可能関数（例えばV≠Lを導くような巨大基数公理を用いた巨大関数）の方が好まれる傾向にあります。

Takayuki Kihara @tri_iro

@non_archimedean J-ランクでの分類の発想は、決定性公理＋従属選択公理を仮定すれば、Lの外に拡張できて、任意の関数に対して順序数での指標を与えることができるとは思いますが、まあさすがに決定性公理を受け入れてくれる人はほとんどいなそうですね……

p進大好きbot @non_archimedean

@tri_iro 決定性公理使った巨大数は見たことがないのですが、ZF+決定性公理+従属選択公理とZFCはどちらがPTOが大きいとか知られているのでしょうか？　PTOが大きくて十分大きな巨大数が定義できるとかなら（みんな公理にこだわらないので）受け入れると思いますよ。特に計算可能巨大数界隈は

p進大好きbot @non_archimedean

@tri_iro ZFC以外の公理系で定義した計算可能関数を使うことがかなり頻繁に行われているので。（ZFCがω無矛盾かどうかはさておきとして標準自然数上での停止性がZFCとは限らない何らかの公理系で証明可能なら、ZFCでも機能する巨大数が作られるだろうという思想だと思います）

Takayuki Kihara @tri_iro

@non_archimedean 決定性公理の無矛盾性は、ZFCの無矛盾性＋無限個のWoodin基数の存在の無矛盾性程度です。

Takayuki Kihara @tri_iro

@non_archimedean すいません「ZFC+無限個のWoodin基数の存在」の無矛盾性のことです。ただ、ZF+AD+DC内では関数の増大階層がある意味できれいに順序数と対応が付けられ、その長さはΘという順序数になるので、その世界の中だと、巨大関数を作るというのは結局はΘ未満の巨大順序数を見つけることと同じになると思います。

Takayuki Kihara @tri_iro

@non_archimedean あ、すいません、関数の増大階層はΘとは対応がつかないですね（一様次数不変写像と巨大関数を対応付けられるというしょうもない間違いをしました）。Θと対応が付くのは、ある意味で「巨大関数を作る仕組み」の方で、巨大関数本体にはどういう順序数が対応づくかはむずかしいところですね

p進大好きbot @non_archimedean

@tri_iro PTOは無矛盾性でなく証明可能整礎性の方の意味でした。（無矛盾性の強さを巨大関数に使う方法は知らないので） 巨大関数を作る仕組みを対応付けられるの面白そうですね。例えば順序数崩壊関数などってその体系でも知られていますか？

Takayuki Kihara @tri_iro

@non_archimedean 可証全域な計算可能関数の範囲は、理論のΠ_2部分だけに依存するのですが、実際の証明はおそらく無矛盾等価性（Π_1部分）だけでなくΠ_2の等価性も導いてそう（たぶん）なので、可証全域な計算可能関数の意味でも無限個のWoodin基数加えたくらいになるのではないでしょうか。

Takayuki Kihara @tri_iro

@non_archimedean 順序数解析の最先端は知らないのですが、順序数崩壊関数についてはわりと小さめの巨大基数にしかまだ適用してるのしか見たことなくて、Woodinレベルのところまで証明論的な手が届いたような話は聞いたことないです

p進大好きbot @non_archimedean

@tri_iro 可証全域な計算可能関数が無限個のWoodin基数加えたものと同じレベルまであるんですか？！　それなら巨大関数作るのに非常に適してそうですね。。

Takayuki Kihara @tri_iro

この会話の後半、あまり詳しくない内容の話をしてしまったので、識者の方、間違いがあったら指摘してください。

p進大好きbot @non_archimedean

@tri_iro 背景としては、ビジービーバー関数に対となる計算可能巨大数で超越整数という概念がありまして、万能チューリングマシンとゲーデル対応で可証全域計算可能関数を形式化して束ねることで作る、可証全域でないけど各標準自然数で停止性が証明可能な関数により実現されます。Halt自体は計算不可能でも

p進大好きbot @non_archimedean

@tri_iro Haltに近い挙動をしているようなぎりぎり計算可能な関数になっているおかげで、「停止性を参照しているからといって計算不可能とは限らない」という例になってます。それを踏まえて、ビジービーバー関数も同様に可証全域計算可能関数とみなせるかが気になる流れだと思いますが、実際計算不可能である

p進大好きbot @non_archimedean

@tri_iro ため、特に全域性の証明可能な計算可能関数とは絶対に一致しない（どの無矛盾な再帰的理論でも＝が証明可能でない）という事を言っているのかと思います。（超越整数は再帰的理論を強めるほど関数が変わっていくので、それと同じくビジービーバーも理論によっては計算可能かを気にしたかもしれません）

p進大好きbot @non_archimedean

@tri_iro （最小の）超越整数は↓で定義される計算可能巨大数です。定義がシュッとしていますので、適宜万能チューリングマシンやゲーデル対応による形式化を脳内で補って下さい。 googology.wikia.com/wiki/Transcend…