[過去ﾛｸﾞ]
巨大数探索スレッド12 [無断転載禁止]©2ch.net (1002ﾚｽ)
巨大数探索スレッド12 [無断転載禁止]©2ch.net http://rio2016.5ch.net/test/read.cgi/math/1484923121/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
458: １３２人目の素数さん [sage] 2017/07/05(水) 22:30:24.81 ID:Wo7Ji0uk ヲヨ数のイメージがいまいち掴みづらいのですが、 たとえば円周率は第一階述語論理の言語で表記するとどうなるのですか？ http://rio2016.5ch.net/test/read.cgi/math/1484923121/458
459: １３２人目の素数さん [sage] 2017/07/06(木) 00:03:48.67 ID:VqI6Xr1R >>456 自然数論単体は矛盾するか矛盾しないかのどちらかであり、1階述語論理の完全性と健全性 により矛盾すればモデルは存在せず、無矛盾であれば存在する 無矛盾であれば、たとえばPA+TとPA+SでBB(x)が取る値が異なることが考えられるのではないか、 ということになるが、どちらの理論も自然数論を含む以上自然数型を部分集合としてもっており、 自然数型をもっていれば異なるモデルに属していても大きさを比べることができ、それなら同じ文字数制限で 出力される最大の数でどちらが大きいかを比べることができ、BB(x)の値が一意に定まる。 自然数型のすべてを持っている必要もない でいいだろうか http://rio2016.5ch.net/test/read.cgi/math/1484923121/459
460: １３２人目の素数さん [sage] 2017/07/06(木) 00:12:35.95 ID:VqI6Xr1R BB(x)はモデルによる制限がない、というのを付け加えるのを忘れていた http://rio2016.5ch.net/test/read.cgi/math/1484923121/460
461: １３２人目の素数さん [sage] 2017/07/06(木) 00:15:50.11 ID:VqI6Xr1R 超準的自然数を出力する(とあるモデルで解釈される)プログラムは有限の値を出力しない =停止しないものと見なされると言うことで http://rio2016.5ch.net/test/read.cgi/math/1484923121/461
462: １３２人目の素数さん [sage] 2017/07/06(木) 00:21:19.45 ID:VqI6Xr1R “加算無限濃度より大きく連続体濃度より小さい濃度の個数”というだけでは 答えが自明にならないため、自明になるまでいろいろ理論を付け加えなければ ある数を命名したことにはならない、というのがラヨ関数のルールのひとつ http://rio2016.5ch.net/test/read.cgi/math/1484923121/462
463: １３２人目の素数さん [sage] 2017/07/06(木) 22:00:17.89 ID:s9ExDxZU つまりチューリングマシンも1階述語論理も自然言語や人間の持つあいまいさから完全には解放されていないというわけだ http://rio2016.5ch.net/test/read.cgi/math/1484923121/463
464: １３２人目の素数さん [sage] 2017/07/07(金) 09:33:49.33 ID:4cWe5aPz >>458 lim[n→inf]Σ[n=0~N]4(-1^n)/2n+1 http://rio2016.5ch.net/test/read.cgi/math/1484923121/464
465: １３２人目の素数さん [sage] 2017/07/07(金) 09:57:48.39 ID:IvvOQVCj >>463 解放されていなんじゃなくて、関わっていない。曖昧な領域は対象外。 http://rio2016.5ch.net/test/read.cgi/math/1484923121/465
466: １３２人目の素数さん [sage] 2017/07/07(金) 14:39:34.01 ID:5pa7VV1Y より曖昧な部分をなんとか扱えるようにしていくことで、より強力なFOOTやFOFTなんかができるわけだし。 >>459 自然数型をもってるというより自然数型と同型な部分構造を持っている、といった方が正確かな http://rio2016.5ch.net/test/read.cgi/math/1484923121/466
467: １３２人目の素数さん [sage] 2017/07/07(金) 14:48:25.77 ID:5pa7VV1Y 「1階述語論理で円周率を表現する」といわれるとまず実数を定義するところから 始めるべきだろうか 1階述語論理じゃ実数「のように見えるもの」までしか作れない。 まぁ普通は見えるだけで十分かもしれない http://rio2016.5ch.net/test/read.cgi/math/1484923121/467
468: １３２人目の素数さん [sage] 2017/07/07(金) 14:54:14.49 ID:5pa7VV1Y 一般的に簡単な具体例を挙げれば分かりやすく説明できるのに、その簡単な具体例がなかなか挙げられない のがこのあたりの難しいところ。 1+1=2をノート一冊まるまるつかって証明するような世界だもの http://rio2016.5ch.net/test/read.cgi/math/1484923121/468
469: １３２人目の素数さん [] 2017/07/08(土) 20:44:57.11 ID:fLvsPSGe 反響があるとは意外。 >>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を構成するのに必要な状態数はせいぜい普通の自然数で足りるだろう。 http://rio2016.5ch.net/test/read.cgi/math/1484923121/469
470: １３２人目の素数さん [sage] 2017/07/08(土) 20:52:06.98 ID:fLvsPSGe >>461で言うところの、超準的自然数を出力するプログラムは停止しないものと見なす、というのは、 それこそまさしく>>457で言った補足入りBB(n)の定義と同じではないか。 いかなる自然数のモデルでも停止する機械、と言っているのだから、停止するまでにかかるステップ数を表す自然数が、 モデルによってあったりなかったりする可能性は無くなる。 >>462については後にしよう。 >>457で後日にすると約束した、補足入りBB(n)の定義においてさえも(普通の自然数に対して)超準的自然数を返すという話が そっくりラヨ関数にも適用できるため、その話をしてからのほうが良さそうだ。 あと、こちらはBB(n)の値の一意性を問題にしてるわけではない。問題にしてるのは、ある程度大きな数nについてのBB(n)、 例えばBB(100)とかBB(10000)とかBB(10^20)とかについて、その返り値がPAのモデルのとりかたによらず存在してるのか、 言い換えると普通の自然数でありえるのか、という存在性についてである。 http://rio2016.5ch.net/test/read.cgi/math/1484923121/470
471: １３２人目の素数さん [sage] 2017/07/08(土) 21:01:01.84 ID:fLvsPSGe >>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だけから存在を証明できる自然数とする。 http://rio2016.5ch.net/test/read.cgi/math/1484923121/471
472: １３２人目の素数さん [sage] 2017/07/08(土) 21:11:33.04 ID:fLvsPSGe ここから内容 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)は計算不能であることとの 矛盾を示すことである。 http://rio2016.5ch.net/test/read.cgi/math/1484923121/472
473: １３２人目の素数さん [sage] 2017/07/08(土) 21:19:18.74 ID:fLvsPSGe 以下のように動作するチューリング機械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" という論理式を作る。 http://rio2016.5ch.net/test/read.cgi/math/1484923121/473
474: １３２人目の素数さん [sage] 2017/07/08(土) 21:28:04.55 ID:fLvsPSGe (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について停止する。 http://rio2016.5ch.net/test/read.cgi/math/1484923121/474
475: １３２人目の素数さん [] 2017/07/08(土) 21:34:19.65 ID:PteOL0NN 皆さんは筑駒中学の入試問題を小学生の知識だけで解けますか？ 純粋な質問ですが、気分を害したらすみません、 http://rio2016.5ch.net/test/read.cgi/math/1484923121/475
476: １３２人目の素数さん [sage] 2017/07/08(土) 21:37:20.76 ID:fLvsPSGe ここで、チューリング機械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だけから存在を保障できる自然数)ではない" 証明終わり http://rio2016.5ch.net/test/read.cgi/math/1484923121/476
477: １３２人目の素数さん [sage] 2017/07/08(土) 21:44:23.58 ID:fLvsPSGe 前述の証明によって、PAがω無矛盾ならBB(n)はある程度大きな(それが10000なのか10^10なのかは分からないが) nについて普通の自然数の値をとることができない、と分かった。 もしPAがω矛盾であるとするなら、BB(n)がPAだけから存在を保障できる自然数になっていても おかしくないが、その場合はPAのモデルがすべて奇妙な性質の自然数を含んでいるということになる。 さて、>>462についてだが、前述の論法を応用すればラヨ関数についても同様のことが言える。 ラヨ関数において、論理式によって命名されたと言えるためには、その論理式をみたす自然数が 集合論のモデルのとり方によらず存在していなければならない。 一階述語論理の完全性から、モデルのとり方によらず存在しているなら、そのことを集合論から 証明可能である。 記号数n以下の論理式を枚挙して前述のチューリング機械Mと似たようなことをする機械を構成すれば、 もし集合論がω無矛盾なら前述のものと同様にラヨ関数Rayo(n)を計算する計算機になる。 しかし、このようなチューリング機械も、一階述語論理の論理式に変換できるから、 そこからラヨ関数の定義との矛盾を導ける。 二階述語論理以降なら完全性が成り立たないからこの論法が使えないのは確かだが、 二階述語論理以降は一階述語論理を包含していて、ラヨ関数より増加が速いはずだから 結局二階以上バージョンのラヨ関数を作っても普通の自然数を返すようにはならない、と言える。 http://rio2016.5ch.net/test/read.cgi/math/1484923121/477
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 525 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
3.360s*