[過去ﾛｸﾞ] 巨大数探索スレッド12 [無断転載禁止]©2ch.net (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
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
473: 2017/07/08(土)21:19 ID:fLvsPSGe(5/9) AAS
以下のように動作するチューリング機械Mを考える。
(1)自然数nが与えられると、桁数n以下の二進数を枚挙する。(0,1,10,11,...,111...111)
(2)それぞれの二進数について、それを万能チューリング機械にコードとして与えたものを、
一階述語論理の論理式に変換する。
(この感覚は、Cook-Levinの定理(充足可能性問題はNP完全問題である)を証明するために
(非決定性)チューリング機械をそっくり命題論理の論理式に置き換えたことの無い
人には理解しがたいかもしれない。)
ここで、ある二進数を渡されたとき万能チューリング機械がどんなPAのモデルのもとでも
停止するようなステップ数があるということを確認する必要がある。
一階述語論理の完全性より、その二進数を渡された万能チューリング機械がモデルに
省13
474: 2017/07/08(土)21:28 ID:fLvsPSGe(6/9) AAS
(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)の証明を試みる子プロセスを生成する
(親プロセスと子プロセスは並列に実行されるものとし、
子プロセスは親プロセスの動作による影響を受けないものとする)
省6
475: 2017/07/08(土)21:34 ID:PteOL0NN(1) AAS
皆さんは筑駒中学の入試問題を小学生の知識だけで解けますか？
純粋な質問ですが、気分を害したらすみません、
476: 2017/07/08(土)21:37 ID:fLvsPSGe(7/9) AAS
ここで、チューリング機械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)の返り値は普通の自然数ではない。
省3
上下前次1-新書関写板覧索設栞歴
あと 526 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.012s