巨大数探索スレッド13
■ このスレッドは過去ログ倉庫に格納されています
とりあえずルベーグ測度を勉強すれば幸せになれると思う >>39
とりあえず、ある程度までは自力で考えてみよう 1/0と0/0を割と自然に追加したのが車輪
でも
(1/0)*0
は1じゃなく0/0になっちゃうが 結局、巨大数を求めるにあたってどこまで奇妙な性質をもつことを許容できるか
という哲学の問題なのかな。
いったんここでは自然数論のモデルに属しうるものはすべて自然数と呼ぶことに
して、以下の4つに分類しよう。特に断りがない場合、証明可能とは古典論理の
もとで証明可能であることを意味する。
(1)存在を直観主義論理のもとでも証明可能な自然数
例: ふぃっしゅ数ver6など、計算可能な手段で求められるもの
(2)存在を証明可能だが、直観主義論理のもとでは証明不能な自然数
例: ある程度大きな入力に対するビジービーバー関数やラヨ関数、
その他の計算不能関数の出力?
(2)の数は、さっきの※みたいな、任意のn∈{0,1,2,...}についてnより大きい
としても無矛盾、といったやや奇妙な性質をもつようになると思われる。
続く (3)存在を仮定するとω矛盾であることが導ける、したがって自然数論からは
おそらく存在が証明不能であるが、無矛盾性は強くしない自然数
おそらく、としたのは自然数論が矛盾していれば何でも証明可能であるため。
例: 「自然数論の矛盾の導出を試みて、導出したら停止する計算機械」
が停止するまでにかかるステップ数
自然数論 + (自然数論は矛盾)という公理を採用すれば停止することを証明可能で、
自然数論が無矛盾ならば(自然数論は無矛盾)は導出できないため、
自然数論が無矛盾ならば、自然数論 + (自然数論は矛盾)もまた無矛盾
よって無矛盾性は強くなっていない。
(4)存在を仮定すると、ω矛盾になるうえ、無矛盾性も強くなるが、
矛盾はしないような自然数
集合論では、大きすぎて存在を仮定すると無矛盾性が強くなるような
濃度のことを巨大基数と呼ぶのだった。いわば、(4)は自然数論版の
巨大基数である。ただしこれについての研究はほとんど無いから、
具体例を挙げるのは難しい。
(3),(4)に属する自然数は超準数で、したがって(1),(2)に属するどの自然数よりも大きい。
(1),(2)は存在を証明できる自然数で、(3),(4)は存在しないとは証明できない自然数である。
(4)に属する自然数はおそらく(3)に属する自然数よりも大きい。 ちなみに>>39にあるような u * 0 = 1となるuについては、実数0は加法の単位元で、
実数1は乗法の単位元なので、1 + 0 = 1と分配法則から
u = u * 1 = u * (1 + 0) = u * 1 + u * 0 = u + 1
よって u = u + 1 両辺からuを引いて 0 = 1 実数の0と1は等しくないので矛盾
だからこのような u は、(1)から(4)のどれにも属さない、
存在を仮定すると矛盾が導ける数、ということになる。 あっ、そうだ。
>>39
さすがに0の逆数っていうのは先述の通り矛盾するからないけど、
どんな実数よりも大きい超実数という数の存在を仮定して色々する
超準解析っていうのがあるよ。 >>47
通常の算術が成り立たなくなることは理解しました。ありがとうございます。
スレチってこともあるのであまり深くは掘り下げないことにします。
そういえばu=u+1って式はuが可算集合濃度だと成立する式ですね。この場合は辺々uを引く操作に意味がないわけですが。 >>45
ビジービーバー関数が存在することに疑問の余地がある? >>45
ビジービーバー関数の何が証明不可能だと言ってる?
Σ(9^9^9)が明確に定義されていて存在することは明らかだよね? 少なくとも、存在することが証明できる数でないと探索にならないのでは?
到達不可能基数のような、巨大基数を仮定すると定義できる巨大自然数
みたいなのがあるの?
関数であればそういう物もあるような気がするけど、
単なる1個の自然数にそういうのがある?
自然数に計算可能も計算不可能も無いよね? スレを計算可能レベルと不可能レベルに別けるのは構わないっちゃあ構わないけど、
不可能レベルだけでそんなに話題があるだろうか? と思って前スレみてみたらそこそこあるな >>24からどうも引っかかるので整理
"ω矛盾とは、自然数 n によって定まる論理式 Q(n) が存在して、次を満たすことをいう。
Q(0), Q(1), Q(2), …が全て証明可能であるが、「∃n: ¬Q(n) 」も証明可能である"
これは正しい
"公理系が無矛盾であれば、対偶を取る事により、ω矛盾の概念が次と同値である事を示せる:
「∃n: Q(n) 」が証明可能であるが、Q(0), Q(1), Q(2), … のいずれも証明可能ではない。"
これは確かにおかしいと思う、Q(0), Q(1), Q(2), … のいずれも証明可能ではないというのは統語論的に
決定できないと言うだけで、Q(0), Q(1), Q(2), … のいずれも反証可能ということではないので スレの統一ルールはないので、計算可能でも不可能でも、自分が好きな話題を出せばいい 数年に1スレ消費するような閑散としたスレッドで、前スレは久々に1年以内に消費した
程度なんだから、話題なんてごった煮でよくて、巨大数に関することは基本的になんでもあり 公理 A に対して、※を満たすくらい十分に大きな定数 M を用意して、
A に可算無限個の式を加えた以下のような公理
A + (0 < BB(M)) + (1 < BB(M)) + (2 < BB(M)) + ...
を A* として、コンパクト性定理より A が無矛盾なら A* も無矛盾
A から ∃n (n = BB(M)) を証明可能とすると、 A のモデルはすべて
BB(M)に該当する数を含む。 一方で A* のモデルではBB(M)は必ず
超準数である。A* が A を含むから、A* のモデルは A のモデルでもあり、
したがって採用する A のモデルによってはBB(M)は超準数になる。
さらに A がω無矛盾であるとすると、 A のモデルには標準モデルもあるため、
採用する A のモデルによってはBB(M)は標準数∈{0,1,2,...}になる。
したがってBB(M)の値はモデルの選び方に依存して変わる。
f が自然数上の計算可能関数とすると、n∈{0,1,2,...}について
0 = f(n), 1 = f(n), 2 = f(n), ...のうちのいずれかは証明可能である。
証明可能な式はどんなモデルを採用しても真なので、標準数を入力したときの
計算可能関数の出力する値はモデルの選び方に依存しない。
当然、0 = BB(M), 1 = BB(M), 2 = BB(M), ...のうちのいずれも証明不能である。
これは、任意の n∈{0,1,2,...} について n < BB(M) としても無矛盾である
ことによる。(n < BB(M) ならば n ≠ BB(M)である)
さっきは暗黙的に標準モデルで考えたために(2)の具体例が(3)の具体例
よりも小さいって言ったけど、超準モデルの中にあるBB(M)だったら
(3)の具体例を超えることも十分に考えられるな。 順序数や基数は整列集合だから
○○を満たす最小
みたいなのがあるわけで
整数だと
nが○○を満たせばn-1も満たすから
そういう形で大きな数を定義するのは無理では? >>57
公理系によってBBの値は変わらんよ
公理系で証明可能だろうが不可能だろうが
BBの値に影響無い
単に選んだ公理系に証明の能力が無いだけ 選んだ公理でマシンの動きが変わるなんて事はあり得ない BB(M)の大きさを語るのに
その大きさをまともに扱えない公理系を使うのが間違い
幼稚園児がBB(4)=14の矛盾を導けないからといって
BB(4)=14と教えれば幼稚園児にとってはBB(4)=14である
と言ってるようなもの 計算可能な関数も
公理によって値を返すかどうか証明不可能なものがあったと思うけど 公理系の強さが順序数で表されるというのは興味深い。
深く勉強してみたいものだ。 二階部分を量化して任意の部分集合は最小値をもつと言えば自然数論の超準モデルと区別できるようになる >>62
少なくともZFCにおいては、BB(4) = 13 が証明されているから、
ZFCのもとで 4 は※をみたすほど大きな数ではない。
無数にある無矛盾な公理系のうちどれを採用すべきかは数学の範囲内
じゃ答えられないし、ある公理がもつ無数のモデルのうちのどのモデル
を採用すべきかも数学の範囲内じゃ答えられない。
しかも、ビジービーバー関数の出力をすべて決定できる無矛盾な公理は必ず
帰納的公理化不能になるから、そんな公理の採用を強制されても神様にしか
扱いきれない。
数学の範囲内で答えられないなら哲学の出番になるけど、俺は哲学的議論
なんてしたくない。決着がつくことはほとんどありえないからだ。
俺はそんな哲学的議論をするより、あくまで数学の範囲内で、
そして人間が扱える公理の範囲内で、考察対象がもつ性質について
述べる方がずっと面白いと思う。 BB(M)が扱える公理系ならどの公理系を選んでも値は同じ
どの公理系を選ぶかなんて考える必要は無い
その辺はBB(4)となんら変わらない 大きい数を競うのに、
実際に値を求める必要は全くなくて、
大小を比較する手段があれば十分 どんな公理を選んでも「決定できない」ものを「定義された」とみなすかどうかの話。
定義できたとみなしたときに、それを「チューリングジャンプ」とか「神託機械によって
計算された」と表現するので、計算可能性理論の領域に入ってくる。 >>25
>「十分大きな自然数Mについて、0 < BB(M), 1 < BB(M), 2 < BB(M), ...が証明可能」
>は証明できてないけど、もっと弱い主張である※ならば簡単に証明できる。
これがおかしい。ビジービーバー関数はFOSTで記述可能、
よって1階述語論理の完全性により、任意の自然数nにつきあるaがただひとつ存在し、BB(n)=aを
証明可能 超準モデルは>>66で否定できる。よってビジービーバー関数の値が超準的自然数にならないように
定義することもできる、というかそういう定義だよな? P(n)はn番目の素数
(sin(1/2)+sin(1/3)+sin(1/5)+sin(1/7)+sin(1/11)+sin(1/13)+・・・+sin(1/P(n)))^2+(1+cos(1/2)+cos(1/3)+cos(1/5)+cos(1/7)+cos(1/11)+cos(1/13)+・・・+cos(1/P(n)))^2≒(n+1)^2 >>66 もっと詳しく。urlでもいい。
>>69 公理とモデルごっちゃにしてない?
>>73 >>25は別に∃a(BB(n)=a)が証明不能とは言ってない。
BB(n)=0,BB(n)=1,...の内のいずれも証明不能なのは>>57の通り>>25の※から導けるけど。 >>76
∃a(BB(n)=a)ではなくBB(n)=aが証明可能、つまりBB(n)=0,BB(n)=1,...の内のいずかが証明可能
であり※は誤り、という主張です >>26はMがどこまでも大きくなればBB(M)もどこまでも大きくなる、ということを証明しているんじゃ? あと
>N個を超える1を出力した時点でそのチューリングマシンは停止しないと判定できる。
N個を超える1を出力した後にその1を消して停止することも考えられるのではないでしょうか? >Mがどこまでも大きくなればBB(M)もどこまでも大きくなる、ということを証明しているんじゃ?
これはこちらの勘違いでした、スマン >>79
BB(n) = 0, BB(n) = 1, ...のいずれかが(帰納的公理化可能な公理から)証明可能なら、
>>26と似たような計算機械、すなわち
BB(n) = 0の証明を試みる子プロセス、BB(n) = 1の証明を試みる子プロセス、...
を次々生成する親プロセスを作り、子プロセスが一個でも証明完了すれば
得られたBB(n)を出力して全プロセスを終了、とすれば子プロセスの1つは証明完了
することは確実なので、BB(n)を計算できる機械が作れ、BB(n)の計算不能性と矛盾 >>80
優勝者よりも多くの1を書きながらそれを消して停止するマシンの存在は
確かにありそうで、その点で>>26には問題があるけど、
「N個を超える」のところは「N*2個」とか「N^2個」、はたまた「2^N個」
「Ackをアッカーマン関数としてAck(N, N)個」と置き換えても停止性問題を
解ける機械が作れるという結論に変わりなく、わざわざAck(N, N)個以上書いた1を
N個未満になるまで消してから停止するマシンがあるのに優勝マシンにはたったの
N個しかテープに1が無い、っていうのは(証明はしてないが)考えにくい。
だから結論は疑っていない。 あ、テープにある1の総数は増やさないけど停止しないものもあるじゃん。
例えば0を読み取ったら状態も文字も変えずただ右にシフトするだけだったら、
空のテープをずっと右に行くだけで停止しないのに1の数は0個のままだから
停止しないと判定されることもない。
>>26 はまずいな... ビジービーバー関数じゃなくて最大ステップ数関数に
譲歩したほうがより安全か。 >>26については>>35でおしまいじゃないの?
どこまで計算しても「計算がいずれは終了するのか永遠に終了しないのかを判定する
一般的アルゴリズムは存在しない」ことが停止性問題。最大値を確実に見積もれたら、
その最大値まで計算すれば判定ができてしまうので停止性問題が解決してしまう。
つまり、>>26の仮定がおかしいということ。 まあ背理法で示す訳だから矛盾を導くためのおかしい仮定をするのは当然だが、
>>35では>>84の例で出した1を出力しないのに停止しないマシンには対処できてない。
いましがた、詳細は省くが、任意のn状態数チューリングマシンに対して、
少なくとも21n状態数チューリングマシンなら1ステップごとに1の数が少なくとも1つは
増えていく、つまりステップ数を数えながら動くマシンを作れることが分かった。
これより、最大ステップ数関数S(n)
= "n状態数チューリングマシンが停止するまでにかかるステップ数の最大値+1"
とすれば、 BB(n) ≦ S(n) ≦ BB(21n) となる。
あとは>>26を改造して n ≧ S(M)が導けたときに n ステップまで動かせば停止性問題解消、
とすれば、あるMが存在し 0 < BB(21M), 1 < BB(21M), ...を加えても無矛盾と言える
ので、∀n (BB(n) < BB(n+1))から、結局は※と同じことを導出できるな。 >>66の任意の部分集合が最小値をもつのと、
超準モデルを否定できるのとのつながりが分からない。 >>26
子プロセスの「矛盾を導出する」のはチューリングマシンと同じ能力の計算機械で出来るの? 停止性問題は任意のチューリングマシンの停止性を判定するアルゴリズムは存在しないというだけで
特定のチューリングマシンの停止性を判定できても矛盾はない・・・よな
超準モデルは必ず無限下降列をもってたと思う それぞれのMにつき、状態数Mのチューリングマシンの停止性を判定するチューリングマシンが
それぞれに存在するだけなら停止性問題に触れない >>86
なるほど。「詳細は省くが」のところが、けっこうすごいことやったのでは? >>88
一階述語論理の健全性と完全性より証明可能⇔恒真
帰納的公理化可能な公理から証明可能な式は枚挙可能
よって証明可能な式を枚挙していれば必ず恒真な式は証明される
>>89
ZFCの無限公理が存在を保証する集合をNとして、ZFCが無矛盾なら、
ZFCに定数記号 v を加え、ZFCに v ∈ N という式を加えても無矛盾
{} ∈ v, {{}} ∈ v, {{}, {{}}} ∈ v , ...の式を有限個加えても無矛盾
よってコンパクト性定理より、
ZFC + (v ∈ N) + ({} ∈ v) + ({{}} ∈ v) + ({{}, {{}}} ∈ v) + ...もまた無矛盾
これをZFC*とすれば、ZFC*のモデルはZFCのモデルでもあるが、超準モデルである。
ZFC*は正則性公理を含むので、ZFC*のモデルの中の集合は∈の無限降下列を持たない。
よって無限降下列が有無を根拠に超準モデルを排除できる訳ではない。
この事実をあえて解釈するなら、超準モデルの中では超準数は有限にしか見えない、
だから自分が超準モデルの中にいるのか標準モデルの中にいるのか分からない、
といったところか。 >>90
自然数Mを入力として与えれば、論理式 n < BB(M)の構成自体は計算可能な手段
で出来るから、 >>26の計算機械は任意のMを入力にとることができる。
だから任意のチューリングマシンの停止性を判定できる一つの計算機械になって矛盾を導ける。
>>91
そんなに気になるか〜。仕方がない。省いた部分を書いてあげる。
テープを 3k, 3k + 1, 3k + 2 番目のセルの3つに分割して、
3k 番目のセルはエミュレート用に、3k + 1, 3k + 2 番目のセルはステップ数の
カウントと制御用に使う。
n状態数マシンのエミュレートを行い、エミュレータが
1ステップ進むたびそこのセルの1つ右と2つ右のセルに合わせて10と書いて、
そこがエミュレータの現在のヘッドの場所だと示す。そして右に進み、3k + 1, 3k + 2
番目のセルが合わせて00になってるところを見つけたら01にして左に戻り、10の
エミュレータの現在ヘッド位置まで戻りエミュレートを再開する。
このようなマシンの構成のために、まずエミュレート用の状態数n個を用意して、
エミュレータのヘッドの状態と読み取った文字(0 or 1)を記憶するための状態として
2n個、今いるセルがエミュレータのヘッド位置から右に 1, 2, 3k, 3k + 1, 3k + 2番目
なのかを記憶するため2n個の5倍、そして往路なのか復路なのかを記憶するのにさらに2倍
よって n + n * 2 * 5 * 2 = 21n 個の状態数があれば足りる。
省いた理由が分かってくれるとうれしいな。 さて、書きたいことは書いたし、もうスレからおいとまするか。
あ、巨大数探索スレだから一つ巨大数を提示してからにしよう。
X = "「自然数論から矛盾の導出を試みて導出したら停止する計算機械」が
停止するまでにかかるステップ数"
自然数論が無矛盾ならXの存在を証明できないし、ゲーデルの不完全性定理より
Xの存在の否定も証明できない。
そして、任意の n ∈ {0, 1, 2, ...}について、 n < X が証明可能、すなわち
0 < X, 1 < X, 2 < X, ... がいずれも証明可能である。
これを巨大数と認めるかどうかは哲学の問題だから俺は言及しない。 >>94
定義が曖昧過ぎませんかねえ
哲学とか言う前に >>91
別にそこはどうでも良いよ
21倍も状態を持てば押さえ込むのは簡単だし
そんなことをしなくとも
シフト関数と大差ないわけだし 自然数論が無矛盾なら停止しない
矛盾していれば停止する
無矛盾を前提にすると停止しないので値は存在しない 任意の超準数uにつき、0でない限りひとつ前の数が存在するのでu-1が存在する。
u-1も超準数である。
以下u-2,u-3,・・・とつづき無限下降列となる
コンパクト性と相いれないのは変だな、自分がどっかで何かを勘違いなり間違いなりしてるんだろう 任意のチューリングマシンは有限時間で停止するかしないかのどちらか
有限個のチューリングマシンの中には有限時間で停止するチューリングマシンが有限個存在する。
有限時間で停止するチューリングマシンの出力する情報の容量なり停止するまでのステップ数なりは有限
有限個の値の中には最大値が存在する。
ビジービーバー関数がこれ以上公理を仮定する必要が無くwell-definedであり、
普通の自然数を返すこと自体は明らかじゃないか? 根本的にビジービーバー関数が定義で標準モデルを指定してないと考えてること自体が間違いかもしらん。 無限下降列をもたないというのは2階の性質になるからコンパクト性と相容れなくていいってことか? >>26は最大シフト関数に置き換えて考えるとして、Mの値が限りなく大きくなれば子プロセス
のプログラムも限りなく複雑になる、ということはない、という証明が必要では ビジービーバー関数
を越えるには
チューリングマシンに神託を加えれば良い
どんどん加えていくことでチューリング次数による
順序構造が出来る
計算可能関数の時と同じように
大きな順序数を作ることで大きな関数が出来る チューリング次数が自然数の時はイメージ湧くけど
チューリング次数がωとかε_0とかも考えられるの? 全ての有限次チューリングマシンの停止性判定が出来るのがω次チューリング機械とか? ふぃっしゅ氏はビジービーバー関数のチューリング次数を数え上げてたけど、それとω次TMとはちょっと違う気もする。チャーチクリーネ順序数上では同じ表記になりそう。
ラヨ数とふぃっしゅ数v4の間の構造の関係もも知りたい。
ふぃっしゅ数v4から何が起こるとラヨに到達するのか。
ラヨ数をチャーチクリーネ順序数表記するとどうなるのか https://ja.m.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E6%AC%A1%E6%95%B0
自然数の集合に対してチューリング次数が決まる
ビジービーバー関数の値となる自然数だけ集めた自然数の集合はチューリング次数0^(1)
この集合を利用できるチューリングマシンのビジービーバー関数の値だけ集めた自然数の集合はチューリンク次数0^(2)
集合0^(n)の情報を全て集めたのが0^(ω)
情報の集め方は、f : N^2 --> N の単射から作れる
当然0^(チャーチクリーネ)等も作れる 可算順序数は基本列が存在するので
全ての可算順序数に対応するチューリング次数である自然数の集合が存在する
チューリング次数は全順序ではなくて、0^(0)と0^(1)の中間のような中途半端な物も存在するが
巨大数探索の為には順序数に対応するチューリング次数だけ考えれば良いような気がする 0^(1)を使えばチャーチクリーネ順序数の基本列が作れるし、
より次数が大きければ、より大きな可算順序数が作れる
大きな順序数から次数の大きな集合を作り
次数の大きな集合から大きな順序数を作る
これを繰り返すことで到達する順序数は非常に大きいが
名前はついているんだろうか recursively inaccessible ordinals
recursively Mahlo ordinals
nonprojectible ordinals
stable ordinals
...
いろいろな巨大可算順序数が書いてありますね 大きな可算順序数αが定義出来たら
巨大数を定義するために
チューリング次数0^(α)の集合たちの中から1個を選ぶ必要があるが、
簡単に1個を選択(定義)することが可能だろうか?
チューリング次数0^(α)の集合たちは可算個存在する
適当に順序を付けて最小が決まれば良いのだが、
最小値があるように順序を決めるのは難しそう
決まらないのであれば、αの基本列を構成して行かねばならない
これは定義が非常に複雑になるので、避けられるなら避けたい 計算不能領域の話題が盛り上がるとは思ってなかったわ。
正直スマンかった。 wikipediaからコピペ
恒真論理式全体の集合は(言語にアリティ 2 以上の述語が一つでも含まれていると)決定可能でない。つまり、
任意に論理式が与えられたとき、それが恒真であるか否かを判定するアルゴリズムは存在しない(「チューリング
マシンの停止問題」を参照)。この結果はアロンゾ・チャーチとアラン・チューリングがそれぞれ独立に導き出した。
正確には、恒真論理式のゲーデル数全体の集合は帰納的でないということである。
それでも、与えられた論理式が恒真であるとき、かつそのときにのみ 1 (yes) を出力して停止するアルゴリズムは
存在する。ただし、恒真でない論理式を入力した場合はこのアルゴリズムは停止しないかもしれない。これを、
恒真論理式全体の集合は準決定可能であるという。これは正確に述べれば、恒真論理式のゲーデル数全体の
集合が帰納的可算であるということである。
ビジービーバー関数の値は決定しているけど計算不可能であるというのはこれで説明できるんじゃないだろうか 上のは恒真式の集合が決定可能である、すなわちアルゴリズムが存在しなければ証明不可能
としていたのが誤りだったということだろうか なんか理解できないのでとりあえずビジービーバー関数の強化版を置いときますね。
Σ^[0](n)=Σ(n)
Σ^[a+1](n)=Σ(Σ^[a](n))
Σ^[0,a](n)=Σ^[a](n)
Σ^[b+1,0](n)=Σ^[b,n](n)
Σ^[b+1,a+1](n)=Σ^[b,Σ^[b+1,a](n)](Σ^[b+1,a](n)) >>118
そのような「”Σ” を使ったあらゆるチューリング計算」の中で最強を指示したのがふぃっしゅ数バージョン4の第1段階目であるs’(1)f(x)。この時点で>>118よりも大きい。
第2段階は「”s’(1)f” を使ったあらゆるチューリング計算」の最強を指示するs’(1)^2f。第3段階、第4段階…と行き、段階を対角化する事で有限段階では辿り着けない第ω段階目のs’(2)fに達する。
「s‘(2)fを使った」が第ω+1段階目のs’(1)s’(2)f。第ω+2のs’(1)^2s’(2)f、第ω+3のs’(1)^3s’(2)f、を対角化した第ω×2のs(2)^2f、それもさらに対角化した第ω^2がs’(3)f。
それをさらに対角化したのが第ω^ωのs’(x)f、そしてさらにそれを63回ss’(x)変換した第(ω^ω)×63の先がふぃっしゅ数バージョン4。 と書いてて思ったこと。こんな風にふぃっしゅ数バージョン4はビジービーバー関数とふぃっしゅ数バージョン3を組み合わせて作られてる。
でもせっかくビジービーバー関数という「あらゆる計算の中で最強の手順を探してくれる」機構があるのに、再帰部分はふぃっしゅ数バージョン3っていう「手作り」機構なんだよね。ここもビジービーバーライズできないものか。 >>109 で recursively inaccessible ordinal 相当の関数が作れる >>119
こういうイメージ?
Σ(x)は、ビジービーバー関数
「f→g(x)」=「『fを使ったあらゆるチューリング計算』の中で最強を指示したものをg(x)とする。」
Σ→Σ^[0](x)
Σ^[a]→Σ^[a+1](x)
Σ^[ω]→Σ^[0,0](x)
Σ^[b,a]→Σ^[b,a+1](x)
Σ^[b,ω]→Σ^[b+1,0](x)
Σ^[ω,ω]→Σ^[0,0,0](x)
Σ^[c,b,a]→Σ^[c,b,a+1](x)
Σ^[c,b,ω]→Σ^[c,b+1,0](x)
Σ^[c,ω,ω]→Σ^[c+1,0,0](x)
Σ^[ω,ω,ω]→Σ^[0,0,0,0](x)
...........
Σ^[ω,...n個...,ω]→Σ^[0,...n+1個...,0](x)
Σ^[ω,...ω個...,ω]→Λ(x)
Λ(Λ(Λ(...63回...Λ(x)...))) ビジービーバー関数みたいな強力な関数に対して
ゴミみたいな量を増やして喜んでるのって
どういう心理?
>>118とかふぃっしゅV4とか 巨大数を生成するシステムが最終的に何を出力するか、計算可能か計算不可能かというのは表層上の
問題な気がする。オラクル無しの1階述語論理の対角化でラヨ関数(本当はFOSTだけど)になる一方で、
1階述語論理よりもはるかに強い高階述語論理を計算可能レベルで実装したCoCの対角化したloader.c
というものもある。
Little Biggedonとか計算可能レベルに応用できそうだがな、どうだろう
真理述語を限定的な停止性の判定に置き換える感じで >>128
どういうとんでもなさを想定してる?
単にa_n=a^nとしてもaを1か-1に近づければ望みの遅さで収束・発散する数列が作れるけどそれじゃ満足しないんだよね? >>131
そうですね
グッドスタイン数列を越えたいです >>129
V7も同じ
強力な武器に対して+1しただけ
そもそも、これらは細部が書いてない為定義として完成してない >>128
増加度の大きな関数の逆関数もどきを使えば作れる
例えば
f(n) を Σ(m)≧nとなる最小のmとして
a[n] = 1 / f(n) みたいな コルモゴロフ複雑度Kを用いて
a[n] = 1 / K(n)
とすると>>134とほぼ同じ 増加度の大きな関数の値が分母にくるようにするわけですか?
すると数列は0に収束する事になるわけですが、分母がすぐ大きくなるから収束速度がとんでもなく早くなる気がします >>133「これら」ってことはラヨ関数も完成してないってこと? は?
>>134のfも>>135のKも
非常に増加度が遅く、無限大に発散する関数
だから、その逆数であるa[n]は非常にゆっくり0に収束する ■ このスレッドは過去ログ倉庫に格納されています