[過去ﾛｸﾞ] 巨大数探索スレッド12 [無断転載禁止]©2ch.net (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
449: ￥ ◆2VB8wsVUoo 2017/06/22(木)07:47 ID:TA0WspoK(7/11) AAS
￥
450: ￥ ◆2VB8wsVUoo 2017/06/22(木)07:47 ID:TA0WspoK(8/11) AAS
￥
451: ￥ ◆2VB8wsVUoo 2017/06/22(木)07:48 ID:TA0WspoK(9/11) AAS
￥
452: ￥ ◆2VB8wsVUoo 2017/06/22(木)07:48 ID:TA0WspoK(10/11) AAS
￥
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をノート一冊まるまるつかって証明するような世界だもの
上下前次1-新書関写板覧索設栞歴
あと 534 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.010s