[過去ﾛｸﾞ] 巨大数探索スレッド12 [無断転載禁止]©2ch.net (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
453: ￥ ◆2VB8wsVUoo 2017/06/22(木)07:48 ID:TA0WspoK(11/11) AAS
￥
454(2): 2017/07/01(土)00:21 ID:7Mq6iIVS(1) AAS
天文学的確率でエントロピーが自然に減少することがなかったっけ？
グラハム数分の１よりは大きいんだろうけど
455: 2017/07/05(水)01:34 ID:6QmaXpqZ(1) AAS
AA省
456(2): 2017/07/05(水)21:01 ID:wGzquPmi(1/2) AAS
ビジービーバー関数BB(n)は、任意の自然数nについてその値が定まると言っていいのだろうか?
例えば連続体仮説でよく知られるように、"可算無限濃度より大きく、連続体濃度より小さい濃度の個数"
の値はZFCのモデルのとり方によって変わり、連続体仮説が真となるモデルなら0、そうでないなら0以外となる。
BB(n)の値も、自然数のモデルのとり方によって変わってしまうことはないか。
"自然数論(ペアノ算術)における妥当な論理式を枚挙し、矛盾を導出したら停止するチューリング機械M"
を構成すると、 これが停止する <=> 自然数論は矛盾 となるから、
自然数論が無矛盾ならこの機械は停止しないはずである。
一方で、自然数論が無矛盾なら自己の無矛盾性は証明できないから、Mが停止しないことを証明できない。
一階述語論理の完全性より、恒真ならば証明可能なので、停止することも停止しないことも証明不能なら
停止するモデルと停止しないモデルの2つがありえる、ということになる。
省8
457(2): 2017/07/05(水)21:06 ID:wGzquPmi(2/2) AAS
では、自然数論の公理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を出力するもの"
省2
458(1): 2017/07/05(水)22:30 ID:Wo7Ji0uk(1) AAS
ヲヨ数のイメージがいまいち掴みづらいのですが、
たとえば円周率は第一階述語論理の言語で表記するとどうなるのですか？
459(2): 2017/07/06(木)00:03 ID:VqI6Xr1R(1/4) AAS
>>456
自然数論単体は矛盾するか矛盾しないかのどちらかであり、1階述語論理の完全性と健全性
により矛盾すればモデルは存在せず、無矛盾であれば存在する
無矛盾であれば、たとえばPA+TとPA+SでBB(x)が取る値が異なることが考えられるのではないか、
ということになるが、どちらの理論も自然数論を含む以上自然数型を部分集合としてもっており、
自然数型をもっていれば異なるモデルに属していても大きさを比べることができ、それなら同じ文字数制限で
出力される最大の数でどちらが大きいかを比べることができ、BB(x)の値が一意に定まる。
自然数型のすべてを持っている必要もない
でいいだろうか
460: 2017/07/06(木)00:12 ID:VqI6Xr1R(2/4) AAS
BB(x)はモデルによる制限がない、というのを付け加えるのを忘れていた
461(1): 2017/07/06(木)00:15 ID:VqI6Xr1R(3/4) AAS
超準的自然数を出力する(とあるモデルで解釈される)プログラムは有限の値を出力しない
=停止しないものと見なされると言うことで
462(2): 2017/07/06(木)00:21 ID:VqI6Xr1R(4/4) AAS
“加算無限濃度より大きく連続体濃度より小さい濃度の個数”というだけでは
答えが自明にならないため、自明になるまでいろいろ理論を付け加えなければ
ある数を命名したことにはならない、というのがラヨ関数のルールのひとつ
463(1): 2017/07/06(木)22:00 ID:s9ExDxZU(1) AAS
つまりチューリングマシンも1階述語論理も自然言語や人間の持つあいまいさから完全には解放されていないというわけだ
464: 2017/07/07(金)09:33 ID:4cWe5aPz(1) AAS
>>458
lim[n→inf]Σ[n=0~N]4(-1^n)/2n+1
465: 2017/07/07(金)09:57 ID:IvvOQVCj(1) AAS
>>463
解放されていなんじゃなくて、関わっていない。曖昧な領域は対象外。
466: 2017/07/07(金)14:39 ID:5pa7VV1Y(1/3) AAS
より曖昧な部分をなんとか扱えるようにしていくことで、より強力なFOOTやFOFTなんかができるわけだし。
>>459
自然数型をもってるというより自然数型と同型な部分構造を持っている、といった方が正確かな
467: 2017/07/07(金)14:48 ID:5pa7VV1Y(2/3) AAS
「1階述語論理で円周率を表現する」といわれるとまず実数を定義するところから
始めるべきだろうか
1階述語論理じゃ実数「のように見えるもの」までしか作れない。
まぁ普通は見えるだけで十分かもしれない
468: 2017/07/07(金)14:54 ID:5pa7VV1Y(3/3) AAS
一般的に簡単な具体例を挙げれば分かりやすく説明できるのに、その簡単な具体例がなかなか挙げられない
のがこのあたりの難しいところ。
1+1=2をノート一冊まるまるつかって証明するような世界だもの
469: 2017/07/08(土)20:44 ID:fLvsPSGe(1/9) AAS
反響があるとは意外。
>>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だけから存在を証明できる自然数(仮に普通の自然数と呼ぼう)と比較可能で、
どんな普通の自然数よりも大きい。
だから、異なるモデルでも大きさを比較できるのはその通りだが、超準的自然数を含んでいるモデルのほうが圧倒的に有利である。
省3
470: 2017/07/08(土)20:52 ID:fLvsPSGe(2/9) AAS
>>461で言うところの、超準的自然数を出力するプログラムは停止しないものと見なす、というのは、
それこそまさしく>>457で言った補足入りBB(n)の定義と同じではないか。
いかなる自然数のモデルでも停止する機械、と言っているのだから、停止するまでにかかるステップ数を表す自然数が、
モデルによってあったりなかったりする可能性は無くなる。
>>462については後にしよう。
>>457で後日にすると約束した、補足入りBB(n)の定義においてさえも(普通の自然数に対して)超準的自然数を返すという話が
そっくりラヨ関数にも適用できるため、その話をしてからのほうが良さそうだ。
あと、こちらはBB(n)の値の一意性を問題にしてるわけではない。問題にしてるのは、ある程度大きな数nについてのBB(n)、
例えばBB(100)とかBB(10000)とかBB(10^20)とかについて、その返り値がPAのモデルのとりかたによらず存在してるのか、
言い換えると普通の自然数でありえるのか、という存在性についてである。
471: 2017/07/08(土)21:01 ID:fLvsPSGe(3/9) AAS
>>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のモデルのとりかたによらず、停止するまでにかかるステップ数である
省9
472: 2017/07/08(土)21:11 ID:fLvsPSGe(4/9) AAS
ここから内容
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)は計算不能であることとの
省1
上下前次1-新書関写板覧索設栞歴
あと 530 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.010s