[過去ﾛｸﾞ] 巨大数探索スレッド12 [無断転載禁止]©2ch.net (1002ﾚｽ)
上下前次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
477: 2017/07/08(土)21:44 ID:fLvsPSGe(8/9) AAS
前述の証明によって、PAがω無矛盾ならBB(n)はある程度大きな(それが10000なのか10^10なのかは分からないが)
nについて普通の自然数の値をとることができない、と分かった。
もしPAがω矛盾であるとするなら、BB(n)がPAだけから存在を保障できる自然数になっていても
おかしくないが、その場合はPAのモデルがすべて奇妙な性質の自然数を含んでいるということになる。
さて、>>462についてだが、前述の論法を応用すればラヨ関数についても同様のことが言える。
ラヨ関数において、論理式によって命名されたと言えるためには、その論理式をみたす自然数が
集合論のモデルのとり方によらず存在していなければならない。
一階述語論理の完全性から、モデルのとり方によらず存在しているなら、そのことを集合論から
証明可能である。
記号数n以下の論理式を枚挙して前述のチューリング機械Mと似たようなことをする機械を構成すれば、
省6
478: 2017/07/08(土)21:52 ID:fLvsPSGe(9/9) AAS
提案されている急増加計算不能関数は、まずビジービーバー関数が常に普通に自然数を返してくれること
が前提となっているように思える。しかし、これは暗黙のうちに前提としていいほど確かなものでもないだろう。
ビジービーバー関数の定義を初めて知った時、みんなはその"あらゆる計算可能関数よりも大きい"
という性質に、その理屈には納得しても気持ち悪さを感じなかっただろうか。
結局のところ、ビジービーバーが大きかったのは、入力が大きいとき、もし返り値が存在するような
PAのモデルを選んでいれば、それが必然的に超準的自然数になるのであって、
いかなる普通の自然数よりも大きいという反則的な性質のものを返していたからだ、ということになる。
常識のように受け入れられているものについて疑問を投げかけてみるのも、大事なことではないだろうか。
479: 2017/07/08(土)22:15 ID:+ACRaVi/(1/5) AAS
超準的自然数は超準的なモデルに属するのであって、ふつうのモデルには属さないんじゃ
480: 2017/07/08(土)22:27 ID:+ACRaVi/(2/5) AAS
我々とは隔絶した存在である超準星人が考えるビジービーバー関数、とかなら
いかなる普通の自然数より大きいという下りはわからんでもない、いや、冗談でなく真面目に
481: 2017/07/08(土)22:39 ID:+ACRaVi/(3/5) AAS
計算可能な関数の集合は可算集合だし、定義可能な範囲であらゆる計算可能な関数より強い関数が
あってもおかしくない、というかあるべきと思うのだわ。
あらゆる定義可能な関数より強い定義可能な〜ってのがあったら気持ち悪い
482: 2017/07/08(土)22:45 ID:+ACRaVi/(4/5) AAS
ビジービーバー関数を超準的な世界で考えるのであれば、停止するかどうかも有限時間の
範囲だけでなく超準的な時間も含めた範囲で考えるべきじゃなかろうか
483: 2017/07/08(土)22:48 ID:+ACRaVi/(5/5) AAS
他にも超準的な世界で考えるとなるといろいろと自明でないことがあって、
普通のビジービーバー関数より強いというのも自明でないかな
484: 2017/07/09(日)00:06 ID:XBkUs4NO(1/2) AAS
ビジービーバー関数の全域性は証明できないわけだから、
PAで存在を証明しようとしてできなかった、というのは当然では
485: 2017/07/09(日)00:09 ID:XBkUs4NO(2/2) AAS
証明できないけど、あると信じて話を進めるかどうか、というだけの話
486(1): 2017/07/09(日)01:09 ID:Ti1B6RCh(1/2) AAS
巨大な数って何に役立ってるのでしょうか？素数は暗号って聞いた
487(1): 2017/07/09(日)01:23 ID:ac91LQvZ(1) AAS
>>486
ある程度以上の巨大さになってくると、数学の研究にちょっと役立つくらいで応用性は無いよ
488: 2017/07/09(日)01:26 ID:Ti1B6RCh(2/2) AAS
>>487
ありがとう
489: ￥ ◆2VB8wsVUoo 2017/07/09(日)02:11 ID:baxN1ASP(1/11) AAS
￥
490: ￥ ◆2VB8wsVUoo 2017/07/09(日)02:11 ID:baxN1ASP(2/11) AAS
￥
491: ￥ ◆2VB8wsVUoo 2017/07/09(日)02:12 ID:baxN1ASP(3/11) AAS
￥
492: ￥ ◆2VB8wsVUoo 2017/07/09(日)02:12 ID:baxN1ASP(4/11) AAS
￥
上下前次1-新書関写板覧索設栞歴
あと 510 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 1.237s*