巨大数探索スレッド12 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
さっさと〜演算子を〜回繰り返すとかいう拡張の限界をもとめて終止符を打てばいいんじゃね？ 演算子の拡張って手段として強いのか弱いのかよくわからん
でも矢印表記とかのわりとクラシックな巨大関数の頃からある手法だから陳腐感は否めないと思う >>391を見直して意味不明だったので改良
拡張ハイパー演算子の定義
A[hyper(N)M]B =
A[hyper(N+B)M-1]A[hyper(N+B)M-1]A[...]A
└── B ──┘
[hyper(N)0] = hyper(N)
3[+1]2 = 3^3 3[+1]3 = 3↑↑3↑↑3 3[+1]4 = 3↑↑↑3↑↑↑3↑↑↑3
3[↑1]2 = 3↑↑↑3 3[↑1]3 = 3↑↑↑↑3↑↑↑↑3 = 3→3→5
3[+2]3 = 3[↑↑1]3[↑↑1]3
= 3[↑↑1](3→3→6)
= 3 hyper(4 + 3→3→6) 3 hyper(4 + 3→3→6) 3 (...) 3
3[+(3[+3]3)]3 = 3[+(3[+3]3 - 1)]3[+(3[+3]3 - 1)]3... ZFC+マーロ基数とマーロ基数を崩壊させた関数。例えばこの二つに違いはあるのかとか、比べる意味がないとか、具体的な大きさが両方わからないけれど知りたい。 ZFC+マーロ基数(が存在するという公理)はこの理論で全域性を証明できるかどうかで強さを計れる。
マーロ基数を崩壊させる方はどう崩壊させるかによる。 マーロ基数や弱コンパクト基数の扱い方がまれによく間違われているような気がする。
Ξ(3,0)=C(Ω_2^3,0)=1-マーロ基数
Ψ[Ξ(3,0)](2,0)=C(Ω_2^2*C(Ω_2^3,0),0)=α→M_αとなる最小の不動点
Ψ[Ψ[Ξ(3,0)](2,0)](1,0)=C(Ω_2^2+Ω,0)=M+1-到達不可能基数
Ψ[Ψ[Ψ[Ξ(3,0)](2,0)](1,0)](0,0)=C(Ω_2^2+C(Ω_2^2+Ω,0),0)=M_M_M_･･･ 何が分かりやすいかってある程度突き詰めたところから先は人それぞれとしか言いようがなくて、
最終的にその人の努力に委ねられるなと思った。 順序数を崩壊させる方法と関数を対角化させる方法ってどういう関係にあるの。 とりあえず崩壊過程が複雑であればそれだけ強力な関数を対角化できる。
話変わるけどあれは論理的帰決と定理、存在論からいえば隔絶された神話的世界
から存在すると言われていることと観測可能であることを同列に語っている点が
どうしてももやもやするんだ。 やりたいことは巨大数の成長率の比べっこだから、じゃあ欲張りクリーク列とかはFGHで評価できるか、みたいな問いになるのかな テトレーション以降の複素数域への拡張は、ただ見解が統一されてないだけで
無数にあるのね 3^3^3^{3^(1/3)}かな
有理数のテトレーションは一般化可能だが無理数のテトレーションとなると見当もつかない ていうか有理数で可能ならその極限としてそのまま無理数に持って行けるんじゃ。 f(0)=ω
f(n+1)=ω^f(n)
f(0)=ω
f(1)=ω^ω
f(2)=ω^ω^ω
f(ω)=ε_0
f(ω+1)=ω^ε_0
f(ω+2)=ω^ω^ε_0
f(ω×2)=ε_0^ε_0
f(ω×3)=ε_0^ε_0^ε_0
f(ω^2)=ε_1
f(ω^2+1)=ω^ε_1
f(ω^2+2)=ω^ω^ε_1
f(ω^2+ω)=ε_0^ε_1
f(ω^2+ω×2)=ε_0^ε_0^ε_1
f(ω^2×2)=ε_1^ε_1
f(ω^2×3)=ε_1^ε_1^ε_1
f(ω^3)=ε_2
f(ω^4)=ε_3
f(ω^ω)=ε_ω
f(ω^ω+1)=ω^ε_ω
f(ω^ω+2)=ω^ω^ε_ω
f(ω^ω+ω)=ε_0^ε_ω
f(ω^ω+ω×2)=ε_0^ε_0^ε_ω
f(ω^ω+ω^2)=ε_1^ε_ω
f(ω^ω+ω^2×2)=ε_1^ε_1^ε_ω
f(ω^ω+ω^3)=ε_2^ε_ω
f(ω^ω+ω^4)=ε_3^ε_ω
f(ω^ω×2)=ε_ω^ε_ω
f(ω^ω×3)=ε_ω^ε_ω^ε_ω
f(ω^(ω+1))=ε_(ω+1)
f(ω^(ω+1)+1)=ω^ε_(ω+1)
f(ω^(ω+1)+2)=ω^ω^ε_(ω+1)
f(ω^(ω+1)+ω)=ε_0^ε_(ω+1)
f(ω^(ω+1)+ω×2)=ε_0^ε_0^ε_(ω+1)
f(ω^(ω+1)+ω^2)=ε_1^ε_(ω+1)
f(ω^(ω+1)+ω^2×2)=ε_1^ε_1^ε_(ω+1)
f(ω^(ω+1)+ω^3)=ε_2^ε_(ω+1)
f(ω^(ω+1)+ω^4)=ε_3^ε_(ω+1)
f(ω^(ω+1)+ω^ω)=ε_ω^ε_(ω+1)
f(ω^(ω+1)+ω^ω×2)=ε_ω^ε_ω^ε_(ω+1)
f(ω^(ω+1)×2)=ε_(ω+1)^ε_(ω+1)
f(ω^(ω+1)×3)=ε_(ω+1)^ε_(ω+1)^ε_(ω+1)
f(ω^(ω+2))=ε_(ω+2)
f(ω^(ω+3))=ε_(ω+3)
f(ω^(ω×2))=ε_(ω×2)
f(ω^(ω×3))=ε_(ω×3)
f(ω^ω^2)=ε_(ω^2)
f(ω^ω^3)=ε_(ω^3)
f(ω^ω^ω)=ε_(ω^ω)
f(ε_0)=ε_(ε_0)
f(ε_(ε_0))=ε_(ε_(ε_0))
f(ε_(ε_(ε_0)))=ε_(ε_(ε_(ε_0)))
f(η_0)=η_0 n状態のチューリングマシンでチューリング完全でないものが読み取ることができる関数の上限
ビジービーバー的な関数の値を求めるのはある程度探究されてるがこっち方面も面白そう たとえばSコンビネータだけ、Kコンビネータだけとか。
Iコンビネータだけだと定数関数、ステップ数を数えあげても後者関数にしかならない。 Kコンビネータだけだと加法の計算しかできないし、ステップ数かぞえてもx+aくらいの
関数にしかならんな。
Sコンビネータはいろいろできそうだ。Sを0、SSSを後者関数としてなんやかやと。
Sコンビネータのみに限定したΞ関数は計算可能なはずだが、どれくらいの強さになるだろう。 Sのみによる計算が終了するかどうかを評価するΩコンビネータを考える。ビッゲドンみたいに高階化してもよい。
KのみIのみと違い計算が終了しないことがある。
S(S(SSS))(S(SSS)(SSS))とか
とても強そう。計算可能? バシク行列もそうだけど、チューリング完全よりも弱い言語を対角化した関数を定義できる言語を・・・
という構造は型システムで表現できる。これは見方を変えれば、チューリング完全な言語による
表現の内、計算が終了すると証明できる形(バシク行列でいう標準形)のみを対角化できる言語を・・・
ということになる。型システムの場合は型検査で証明する。バシク行列システムでは
まだもろもろ証明もできてないし、標準形の判断方法も定まっていない。
しかしそれらの問題を解決できたら、CoCはおろかCICをはるかに上回る証明支援システム
として扱うことができるのではなかろうか。 このレベルになると計算可能レベルも計算不可能レベルと同じように言語を開発して殴り合う戦いに
なりそうだ。
出来上がったら証明支援ツールにそのまま応用が利くし、プログラミング業界にも何か恩恵があるかもしれない、
とか適当なことを言ってみる チューリング完全な言語で遺伝的アルゴリズムとか使って巨大数を生成したら
ビジービーバーにどこまで迫れるんだろう？
チューリング完全をはずれて真の乱数生成装置とかが使えると仮定したら
ビジービーバーに追いつく可能性も出てくるんだろうか。 計算可能性の証明って、システムが強力であればある程、必然的になにかしらの巨大基数公理を
生み出すのだな ε0は切がいい順序数のように見えるけどその次の切の良い順序数ってГ0あたり？ 巨大基数公理ってどこまで巨大になっていくんだろ
計算不可能レベルの巨大数も可算基数も不可算基数も、大きさのイメージとかが掴めない
それぞれの違いがわかりやすい解説とか無いのかな >>419
ε_0は文字が変わるから切りがいいように見えて本質はω↑↑ωっていうだけだよ。
ω^ωに比べて大したことない。 >>419
多変数ヴェブレン関数で表すと、
ε_0(イプシロン・ノート) = φ(1,0)
Г_0(フェファーマン・シュッテの順序数) = φ(1,0,0)
どちらの順序数もヴェブレン関数の変数が1個増えるターニングポイントという点では
キリがいいのかも
（※同様の順序数として
ω = φ(1)、アッカーマン順序数φ(1,0,0,0)、小ヴェブレン順序数φ(1,0,…,0)(0がω個)
等がある模様） しかし>>421さんを見るとε_0が人為的に文字に置き換えられてる感も否めなくなるな…
ε0より大きい順序数でもわざわざ新しい記号を使わなくともωだけでも表せそうな気もするし
（例えばω↑↑↑↑ω、{ω,ω,1,2}みたいな感じで）
その方が直感的で分かり易そうなんだが今の所そういう表し方は見た事が無い
やはりこの表し方だと何かしらの問題があるのだろうか？ バードがやっているよ
http://mrob.com/users/chrisb/Beyond_Nested_Arrays_I.pdf
ここに書かれているように、
ω^^(ω+1) = ω^(ω^^ω) = ω^ε_0 = ε_0
となってしまうため、通常の計算規則だとε_0よりも大きくならない。
そこで、バードは
ω^^(ω+1) = ω^(ε_0+1)
かつ、 ω^^β = ε_αのときに
ω^^(β+1) = ω^(ε_α+1)
であると「定義を変える」ことで、ωに関する演算の定義を拡張している。
ただ、このように「定義を変える」ことは必ずしも自明のことではないので、
表記するときにはいちいちことわらなければならないし、
数学的には Veblen 階層や順序数崩壊関数を使う方が自然なので、
そのような表記法はあまり一般的ではない。 {ω,ω,1,2}みたいなのを発展させたのがレギオン配列とかじゃないの？ そう。それで、ω^^(ω+1)がε_0よりも強くならないから、BEAFのテトレーション配列
以上は定義がうまくできていない、と Hyp cos が指摘をした、ということが「巨大数論」の
221ページに書かれている。 なるほど、ありがとう
という事は矢印表記は右結合だからω↑↑…↑↑ωの矢印を幾ら増やそうが
この調子でその拡張であるチェーンやBEAFを使おうが
結局はω↑↑(ωの式)の形に行きついてε_0止まりなのか…
超限順序数ならではの奇妙な現象だ
左結合である下矢印表記を使えばより大きくできるのかとか
そもそもなぜω^ε_0 = ε_0が成り立つのかとか
まだまだ謎が尽きないな
自分でももっと色々調べてみた方がよさそうだ 配列を記述する配列の計算ルールを左結合になるよう変えて成り立つようにしてたよな 御風結界
巨大数を作ったけど
近似してくれないですか
画像で説明したいけど
どう貼り付けたらいいの
ふぃしゅ数ver1.2よりはでかいのはわかってるけど
自分でも大きさがわからない
バード数よりも大きい気がする
タワー数とチェーン表記に行きつくけど
行きつかないくらいでかい感じがする
バードの拡張表記をさらに拡張した感じの巨大数
合成前のスタート地点を(3.3.3.3)$(3.3)と配列表記では定義する ★★★数学徒は論理的な考察により客観的に暮らし、日頃から深い学術を志すべき。★★★
￥ ω(↑^ω)ωの濃度はアレフ0、つまり可算だと言っているだけで、特に不思議はないような。 ★★★馬鹿板は悪い習慣であり、大脳が劣化します。なので早く止めましょう。★★★
￥ 天文学的確率でエントロピーが自然に減少することがなかったっけ？
グラハム数分の１よりは大きいんだろうけど >>454の現象
＜宇宙の取りりうる全パターンの順列
＜グラハム数 ビジービーバー関数BB(n)は、任意の自然数nについてその値が定まると言っていいのだろうか?
例えば連続体仮説でよく知られるように、"可算無限濃度より大きく、連続体濃度より小さい濃度の個数"
の値はZFCのモデルのとり方によって変わり、連続体仮説が真となるモデルなら0、そうでないなら0以外となる。
BB(n)の値も、自然数のモデルのとり方によって変わってしまうことはないか。
"自然数論(ペアノ算術)における妥当な論理式を枚挙し、矛盾を導出したら停止するチューリング機械M"
を構成すると、 これが停止する <=> 自然数論は矛盾 となるから、
自然数論が無矛盾ならこの機械は停止しないはずである。
一方で、自然数論が無矛盾なら自己の無矛盾性は証明できないから、Mが停止しないことを証明できない。
一階述語論理の完全性より、恒真ならば証明可能なので、停止することも停止しないことも証明不能なら
停止するモデルと停止しないモデルの2つがありえる、ということになる。
(一階述語論理の完全性と呼ばれるものは、ゲーデルの第一不完全性定理で言うところの完全性(任意の論理式に
ついて、その肯定か否定のどちらかが証明可能)とは全く意味が異なることに注意)
そもそもチューリング機械Aが停止するとは、"Aがnステップ目で停止状態"を意味する論理式H_A(n)に対し、
∃n (H_A(n))が真であることだと言える。
∃n (H_M(n))が成り立つモデルと成り立たないモデルがあるとはどういうことか。
単純に、∃n (H_M(n))が成り立つ自然数論のモデルはより多くの自然数を含んでいる、ということである。
(集合論で言うところの、巨大基数公理が成り立つモデルのほうが、そうでないモデルよりたくさんの
集合を含んでいることに似ている) では、自然数論の公理PAに、∃n (H_M(n))を加えたことによって追加される自然数とは何か。
自然数論が無矛盾なら、Mは1ステップ目で停止しないだろう。同様に、2,3,4,...ステップ目でも停止しない。
追加される自然数はMが停止するまでにかかるステップ数だから、これをcとすると、
0<c, 1<c, 2<c, 3<c, 4<c,...が成り立つことになる。つまり、PAだけから存在を証明できるいかなる自然数
よりもcのほうが大きい、という奇妙な性質があることが分かる。このcが超準的自然数と呼ばれるもので、
これを含むモデルは超準モデルと呼ばれる。
冒頭の話に戻ると、状態数m以下でMを構成できるなら、Mが停止するモデルを選択すれば、
BB(m)の値は超準的自然数になってしまい、意味をなさなくなってしまう。
ならばBB(n)の定義に補足を加え、
"状態数n以下で(いかなる自然数のモデルでも)停止する機械のうち最も多く1を出力するもの"
とすればこのような問題は起きないと思うかもしれない。
実はそれでもBB(n)の値は超準的自然数になってしまうのだが、それはまた後日の話とする。 ヲヨ数のイメージがいまいち掴みづらいのですが、
たとえば円周率は第一階述語論理の言語で表記するとどうなるのですか？ >>456
自然数論単体は矛盾するか矛盾しないかのどちらかであり、1階述語論理の完全性と健全性
により矛盾すればモデルは存在せず、無矛盾であれば存在する
無矛盾であれば、たとえばPA+TとPA+SでBB(x)が取る値が異なることが考えられるのではないか、
ということになるが、どちらの理論も自然数論を含む以上自然数型を部分集合としてもっており、
自然数型をもっていれば異なるモデルに属していても大きさを比べることができ、それなら同じ文字数制限で
出力される最大の数でどちらが大きいかを比べることができ、BB(x)の値が一意に定まる。
自然数型のすべてを持っている必要もない
でいいだろうか BB(x)はモデルによる制限がない、というのを付け加えるのを忘れていた 超準的自然数を出力する(とあるモデルで解釈される)プログラムは有限の値を出力しない
=停止しないものと見なされると言うことで “加算無限濃度より大きく連続体濃度より小さい濃度の個数”というだけでは
答えが自明にならないため、自明になるまでいろいろ理論を付け加えなければ
ある数を命名したことにはならない、というのがラヨ関数のルールのひとつ つまりチューリングマシンも1階述語論理も自然言語や人間の持つあいまいさから完全には解放されていないというわけだ >>458
lim[n→inf]Σ[n=0~N]4(-1^n)/2n+1 >>463
解放されていなんじゃなくて、関わっていない。曖昧な領域は対象外。 より曖昧な部分をなんとか扱えるようにしていくことで、より強力なFOOTやFOFTなんかができるわけだし。
>>459
自然数型をもってるというより自然数型と同型な部分構造を持っている、といった方が正確かな 「1階述語論理で円周率を表現する」といわれるとまず実数を定義するところから
始めるべきだろうか
1階述語論理じゃ実数「のように見えるもの」までしか作れない。
まぁ普通は見えるだけで十分かもしれない 一般的に簡単な具体例を挙げれば分かりやすく説明できるのに、その簡単な具体例がなかなか挙げられない
のがこのあたりの難しいところ。
1+1=2をノート一冊まるまるつかって証明するような世界だもの 反響があるとは意外。
>>459 多分勘違いをしていると思う。
まず、集合論でも連続体仮説が成り立つモデルと成り立たないモデルがとれることからも分かるように、
一般に、ある一つの無矛盾な公理系に対して、それが成り立つモデルはたくさん存在する。
そして、PA + ∃n (H_M(n))のモデルは、当然PAも成り立つから、同時にPAのモデルでもある。
(PA + ∃n (H_M(n))は矛盾していない。PAが無矛盾なら、PAから ¬∃n (H_M(n))が導出されてしまう心配は無いのだから)
PAのモデルに属していれば自然数であるから、∃n (H_M(n))の証拠となる超準的自然数さえも、自然数であることに
変わりなく、0,1,2のようなPAだけから存在を証明できる自然数(仮に普通の自然数と呼ぼう)と比較可能で、
どんな普通の自然数よりも大きい。
だから、異なるモデルでも大きさを比較できるのはその通りだが、超準的自然数を含んでいるモデルのほうが圧倒的に有利である。
超準的自然数を出してしまえば、超準的自然数を含まないモデルに属する自然数に必ず勝てるのだから。
そして機械Mの状態数がm以下であれば、BB(m)には超準的自然数が採用されるだろう。
機械Mを構成するのに必要な状態数はせいぜい普通の自然数で足りるだろう。 >>461で言うところの、超準的自然数を出力するプログラムは停止しないものと見なす、というのは、
それこそまさしく>>457で言った補足入りBB(n)の定義と同じではないか。
いかなる自然数のモデルでも停止する機械、と言っているのだから、停止するまでにかかるステップ数を表す自然数が、
モデルによってあったりなかったりする可能性は無くなる。
>>462については後にしよう。
>>457で後日にすると約束した、補足入りBB(n)の定義においてさえも(普通の自然数に対して)超準的自然数を返すという話が
そっくりラヨ関数にも適用できるため、その話をしてからのほうが良さそうだ。
あと、こちらはBB(n)の値の一意性を問題にしてるわけではない。問題にしてるのは、ある程度大きな数nについてのBB(n)、
例えばBB(100)とかBB(10000)とかBB(10^20)とかについて、その返り値がPAのモデルのとりかたによらず存在してるのか、
言い換えると普通の自然数でありえるのか、という存在性についてである。 >>457の続き
証明の前に、用語の確認をしておく。
公理がω矛盾であるとは、ある論理式Q(n)について、∃n ∈ (自然数)(Q(n))が証明可能であるのに、
Q(0),Q(1),Q(2),...のうちのいずれも証明不能であることである。
公理がω無矛盾であるとは、任意の論理式Q(n)について、∃n ∈ (自然数)(Q(n))が証明可能ならば、
Q(0),Q(1),Q(2),...のうちのどれかが証明可能であることである。
ある公理がω無矛盾ならば、その公理は無矛盾でもある。
したがって自己の無矛盾性を証明できない公理は、自己のω無矛盾性も証明できない。
BB(n)の定義は
"状態数n以下で、自然数論PAのモデルのとりかたによらず、停止するまでにかかるステップ数である
自然数が存在するようなチューリング機械のうち、最も多くの1を出力するものが出力する1の個数"
このままだと扱いにくいので、次に定義するS(n)によって代用する。
"万能チューリング機械に、桁数n以下の二進数でコードを与えエミュレートさせ、PAのモデルのとりかた
によらず停止するまでのステップ数である自然数が存在するコードのうち、最後に停止するものの総ステップ数+1"
S(n)がBB(n)の性質を反映しているということは明らかだろう。
証明することは、
"(PAがω無矛盾 ∧ ある自然数Nについて∃n (n = S(N))がPAのモデルによらず真 ) => 矛盾"
したがって "自然数論PAがω矛盾 ∨ ∃n (n = S(N))がモデルによっては偽 )"
なお、NはPAだけから存在を証明できる自然数とする。 ここから内容
PAがω無矛盾 ∧ ある自然数Nについて∃n (n = S(N))がPAのモデルによらず真
と仮定する。
∃n (n = S(N))がPAのモデルによらず真であるから、
一階述語論理の完全性(恒真 => 証明可能)より、∃n (n = S(N))はPAから証明可能
※PAがω無矛盾なので、0 = S(N), 1 = S(N), 2 = S(N),...のうちのいずれかがPAから証明可能
これからすることは、 n = S(N)という式を具体的な論理式に変換し、
それができたら 0 = S(N), 1 = S(N),...の証明の試みを(順番に子プロセスを生成しながら)
並列的に行うチューリング機械が作れ、かつそのような機械が※より停止することが保障されることから、
S(N)を実際に計算できてしまうということを示し、一般的にS(n)は計算不能であることとの
矛盾を示すことである。 以下のように動作するチューリング機械Mを考える。
(1)自然数nが与えられると、桁数n以下の二進数を枚挙する。(0,1,10,11,...,111...111)
(2)それぞれの二進数について、それを万能チューリング機械にコードとして与えたものを、
一階述語論理の論理式に変換する。
(この感覚は、Cook-Levinの定理(充足可能性問題はNP完全問題である)を証明するために
(非決定性)チューリング機械をそっくり命題論理の論理式に置き換えたことの無い
人には理解しがたいかもしれない。)
ここで、ある二進数を渡されたとき万能チューリング機械がどんなPAのモデルのもとでも
停止するようなステップ数があるということを確認する必要がある。
一階述語論理の完全性より、その二進数を渡された万能チューリング機械がモデルに
よらず停止するなら、そのことをPAから証明可能である。
PAから証明可能なら、その二進数を渡された万能チューリング機械が停止状態になる
ようなステップ数aが存在する、という論理式の証明を(PAの妥当な論理式を枚挙することで)
試みるチューリング機械が停止する。
ゆえに、次に行うべきことは、
(3)(1)で枚挙した各二進数について、それを入力された万能チューリング機械が停止する
という意味の論理式を(2)で作った論理式を利用して作る
(4)(3)で作ったそれぞれの論理式について、その証明を試みるチューリング機械のコードを生成する
(5)(4)で作った各コードについても、それが停止するという意味の論理式を同様に作る
(6)(1)で枚挙した各二進数について、
"(5)で作った論理式(が真) => その二進数を万能チューリング機械与えたときに停止するまでに
かかるステップ数((2)で作った論理式を利用して作れる論理式) < x"
という論理式を作る。 (7)(6)で作った論理式を、すべて∧でつなげた論理式をP(x)として、
yを自由変数とする論理式"P(y)∧∀x(P(x) => y ≦ x)" を作る。
ここで作られている論理式が、まさしく
"任意の、コード長n以下の、いかなるPAのモデルでも停止するコードが停止するまでに
かかるステップ数よりも大きい最小の数はyである"という意味になっていることに注意しよう。
今まで漠然とy = S(n)と書いてきた式を、しっかり一階述語論理の論理式に直したものだといってもよい。
(8)k = 0とする。
(9)(7)で作った論理式を、y = S(n)と表すとして、k = S(n)の証明を試みる子プロセスを生成する
(親プロセスと子プロセスは並列に実行されるものとし、
子プロセスは親プロセスの動作による影響を受けないものとする)
(10)どの子プロセスも停止していないなら、kを1増やして(9)に戻る
(11)どれか1つでも子プロセスが停止したなら、その停止した子プロセスが証明した論理式から、
S(n)の値を得られるため、その値を返す。
(12)終了
Mが停止しない可能性があるとしたら、それは(9),(10)のループ処理で、無限ループすることであるが、
それは※よりありえない。よってMは任意のnについて停止する。 皆さんは筑駒中学の入試問題を小学生の知識だけで解けますか？
純粋な質問ですが、気分を害したらすみません、 ここで、チューリング機械Mを万能チューリング機械でエミュレートできるようにコード化したもの
を<M>とし、機械Mに自然数nを与えた場合のコードを、nを二進数にしたものを<n>として、
<M><n>と表記する。<M>のコード長をmとすると、mは普通の自然数であり、<n>のコード長はlog_2(n)
である。
よって <M><n> のコード長は m + log_2(n)であり、もしNが十分大きな普通の自然数ならば、
m + log_2(N) < N が成り立つ。
しかし、 <M><N> をエミュレートするとS(N)を返すので、コード長N以下なのにS(N)の値を返すという
点で、S(n)の定義と矛盾 (ベリーのパラドックスに似る)
したがって、背理法より、自然数論PAがω矛盾であるか、またはある程度大きな普通の自然数Nについて
S(N)の返り値は普通の自然数ではない。
よってある程度大きな普通の自然数Nについて、
"自然数論PAがω無矛盾ならば、BB(N)の値は普通の自然数(PAだけから存在を保障できる自然数)ではない"
証明終わり 前述の証明によって、PAがω無矛盾ならBB(n)はある程度大きな(それが10000なのか10^10なのかは分からないが)
nについて普通の自然数の値をとることができない、と分かった。
もしPAがω矛盾であるとするなら、BB(n)がPAだけから存在を保障できる自然数になっていても
おかしくないが、その場合はPAのモデルがすべて奇妙な性質の自然数を含んでいるということになる。
さて、>>462についてだが、前述の論法を応用すればラヨ関数についても同様のことが言える。
ラヨ関数において、論理式によって命名されたと言えるためには、その論理式をみたす自然数が
集合論のモデルのとり方によらず存在していなければならない。
一階述語論理の完全性から、モデルのとり方によらず存在しているなら、そのことを集合論から
証明可能である。
記号数n以下の論理式を枚挙して前述のチューリング機械Mと似たようなことをする機械を構成すれば、
もし集合論がω無矛盾なら前述のものと同様にラヨ関数Rayo(n)を計算する計算機になる。
しかし、このようなチューリング機械も、一階述語論理の論理式に変換できるから、
そこからラヨ関数の定義との矛盾を導ける。
二階述語論理以降なら完全性が成り立たないからこの論法が使えないのは確かだが、
二階述語論理以降は一階述語論理を包含していて、ラヨ関数より増加が速いはずだから
結局二階以上バージョンのラヨ関数を作っても普通の自然数を返すようにはならない、と言える。 提案されている急増加計算不能関数は、まずビジービーバー関数が常に普通に自然数を返してくれること
が前提となっているように思える。しかし、これは暗黙のうちに前提としていいほど確かなものでもないだろう。
ビジービーバー関数の定義を初めて知った時、みんなはその"あらゆる計算可能関数よりも大きい"
という性質に、その理屈には納得しても気持ち悪さを感じなかっただろうか。
結局のところ、ビジービーバーが大きかったのは、入力が大きいとき、もし返り値が存在するような
PAのモデルを選んでいれば、それが必然的に超準的自然数になるのであって、
いかなる普通の自然数よりも大きいという反則的な性質のものを返していたからだ、ということになる。
常識のように受け入れられているものについて疑問を投げかけてみるのも、大事なことではないだろうか。 超準的自然数は超準的なモデルに属するのであって、ふつうのモデルには属さないんじゃ 我々とは隔絶した存在である超準星人が考えるビジービーバー関数、とかなら
いかなる普通の自然数より大きいという下りはわからんでもない、いや、冗談でなく真面目に 計算可能な関数の集合は可算集合だし、定義可能な範囲であらゆる計算可能な関数より強い関数が
あってもおかしくない、というかあるべきと思うのだわ。
あらゆる定義可能な関数より強い定義可能な〜ってのがあったら気持ち悪い ビジービーバー関数を超準的な世界で考えるのであれば、停止するかどうかも有限時間の
範囲だけでなく超準的な時間も含めた範囲で考えるべきじゃなかろうか 他にも超準的な世界で考えるとなるといろいろと自明でないことがあって、
普通のビジービーバー関数より強いというのも自明でないかな ビジービーバー関数の全域性は証明できないわけだから、
PAで存在を証明しようとしてできなかった、というのは当然では 証明できないけど、あると信じて話を進めるかどうか、というだけの話 巨大な数って何に役立ってるのでしょうか？素数は暗号って聞いた >>486
ある程度以上の巨大さになってくると、数学の研究にちょっと役立つくらいで応用性は無いよ ■ このスレッドは過去ログ倉庫に格納されています
