巨大数探索スレッド12 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
>>458
lim[n→inf]Σ[n=0~N]4(-1^n)/2n+1 >>463
解放されていなんじゃなくて、関わっていない。曖昧な領域は対象外。 より曖昧な部分をなんとか扱えるようにしていくことで、より強力なFOOTやFOFTなんかができるわけだし。
>>459
自然数型をもってるというより自然数型と同型な部分構造を持っている、といった方が正確かな 「1階述語論理で円周率を表現する」といわれるとまず実数を定義するところから
始めるべきだろうか
1階述語論理じゃ実数「のように見えるもの」までしか作れない。
まぁ普通は見えるだけで十分かもしれない 一般的に簡単な具体例を挙げれば分かりやすく説明できるのに、その簡単な具体例がなかなか挙げられない
のがこのあたりの難しいところ。
1+1=2をノート一冊まるまるつかって証明するような世界だもの 反響があるとは意外。
>>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を構成するのに必要な状態数はせいぜい普通の自然数で足りるだろう。 >>461で言うところの、超準的自然数を出力するプログラムは停止しないものと見なす、というのは、
それこそまさしく>>457で言った補足入りBB(n)の定義と同じではないか。
いかなる自然数のモデルでも停止する機械、と言っているのだから、停止するまでにかかるステップ数を表す自然数が、
モデルによってあったりなかったりする可能性は無くなる。
>>462については後にしよう。
>>457で後日にすると約束した、補足入りBB(n)の定義においてさえも(普通の自然数に対して)超準的自然数を返すという話が
そっくりラヨ関数にも適用できるため、その話をしてからのほうが良さそうだ。
あと、こちらはBB(n)の値の一意性を問題にしてるわけではない。問題にしてるのは、ある程度大きな数nについてのBB(n)、
例えばBB(100)とかBB(10000)とかBB(10^20)とかについて、その返り値がPAのモデルのとりかたによらず存在してるのか、
言い換えると普通の自然数でありえるのか、という存在性についてである。 >>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だけから存在を証明できる自然数とする。 ここから内容
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)は計算不能であることとの
矛盾を示すことである。 以下のように動作するチューリング機械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"
という論理式を作る。 (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について停止する。 皆さんは筑駒中学の入試問題を小学生の知識だけで解けますか？
純粋な質問ですが、気分を害したらすみません、 ここで、チューリング機械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だけから存在を保障できる自然数)ではない"
証明終わり 前述の証明によって、PAがω無矛盾ならBB(n)はある程度大きな(それが10000なのか10^10なのかは分からないが)
nについて普通の自然数の値をとることができない、と分かった。
もしPAがω矛盾であるとするなら、BB(n)がPAだけから存在を保障できる自然数になっていても
おかしくないが、その場合はPAのモデルがすべて奇妙な性質の自然数を含んでいるということになる。
さて、>>462についてだが、前述の論法を応用すればラヨ関数についても同様のことが言える。
ラヨ関数において、論理式によって命名されたと言えるためには、その論理式をみたす自然数が
集合論のモデルのとり方によらず存在していなければならない。
一階述語論理の完全性から、モデルのとり方によらず存在しているなら、そのことを集合論から
証明可能である。
記号数n以下の論理式を枚挙して前述のチューリング機械Mと似たようなことをする機械を構成すれば、
もし集合論がω無矛盾なら前述のものと同様にラヨ関数Rayo(n)を計算する計算機になる。
しかし、このようなチューリング機械も、一階述語論理の論理式に変換できるから、
そこからラヨ関数の定義との矛盾を導ける。
二階述語論理以降なら完全性が成り立たないからこの論法が使えないのは確かだが、
二階述語論理以降は一階述語論理を包含していて、ラヨ関数より増加が速いはずだから
結局二階以上バージョンのラヨ関数を作っても普通の自然数を返すようにはならない、と言える。 提案されている急増加計算不能関数は、まずビジービーバー関数が常に普通に自然数を返してくれること
が前提となっているように思える。しかし、これは暗黙のうちに前提としていいほど確かなものでもないだろう。
ビジービーバー関数の定義を初めて知った時、みんなはその"あらゆる計算可能関数よりも大きい"
という性質に、その理屈には納得しても気持ち悪さを感じなかっただろうか。
結局のところ、ビジービーバーが大きかったのは、入力が大きいとき、もし返り値が存在するような
PAのモデルを選んでいれば、それが必然的に超準的自然数になるのであって、
いかなる普通の自然数よりも大きいという反則的な性質のものを返していたからだ、ということになる。
常識のように受け入れられているものについて疑問を投げかけてみるのも、大事なことではないだろうか。 超準的自然数は超準的なモデルに属するのであって、ふつうのモデルには属さないんじゃ 我々とは隔絶した存在である超準星人が考えるビジービーバー関数、とかなら
いかなる普通の自然数より大きいという下りはわからんでもない、いや、冗談でなく真面目に 計算可能な関数の集合は可算集合だし、定義可能な範囲であらゆる計算可能な関数より強い関数が
あってもおかしくない、というかあるべきと思うのだわ。
あらゆる定義可能な関数より強い定義可能な〜ってのがあったら気持ち悪い ビジービーバー関数を超準的な世界で考えるのであれば、停止するかどうかも有限時間の
範囲だけでなく超準的な時間も含めた範囲で考えるべきじゃなかろうか 他にも超準的な世界で考えるとなるといろいろと自明でないことがあって、
普通のビジービーバー関数より強いというのも自明でないかな ビジービーバー関数の全域性は証明できないわけだから、
PAで存在を証明しようとしてできなかった、というのは当然では 証明できないけど、あると信じて話を進めるかどうか、というだけの話 巨大な数って何に役立ってるのでしょうか？素数は暗号って聞いた >>486
ある程度以上の巨大さになってくると、数学の研究にちょっと役立つくらいで応用性は無いよ ビジービーバー関数の全域性は１階述語論理で記述できる以上恒真であれば証明できる △△△馬鹿板をスルのは不埒な行為であり、脳が悪くなります。そやしセンでもヨロシ。△△△
￥ >>454が連続して起こることで宇宙が熱的死を起こしても急に不死鳥のごとく復活する可能性が
考えられるという説を昔なにかの本で読んだ。 ビジービーバー関数の全域性を証明するためには「ビジービーバー関数が全域関数である」と
同値の公理を入れない限り無理では >>502
お前の前提としてる公理系って何よって話。 >>513
それを問われるのは>>499では
「証明できる」と言ってるんだから ★★★馬鹿板は悪い習慣であり、大脳が崩壊します。なので早く止めましょう。★★★
￥ >>514
特に断りがなければZFCとするのが通常じゃね？
ZFCならビジービーバーの全域性は証明できたはず。
ZFCでないというなら>>514が立場をはっきりさせないと。 ★★★馬鹿板は悪い習慣であり、大脳が崩壊します。なので早く止めましょう。★★★
￥ >>516
ビジービーバー関数 BB(n) は（最大でも） n=7910 でZFCの限界を超えるので
ZFCで全域性の証明は無理
https://arxiv.org/abs/1605.04343 ★★★数学徒は馬鹿板をしない生活を送り、日頃から真面目に学問に精進すべき。★★★
￥ sage入れるところ間違えてない？
再帰関数すべてを支配できる公理をもってないと証明はできないだろう。しかし1階述語論理の
完全性から、理論と言うか、1階述語論理、より限定してFOSTによって記述された定義からその
まま証明できるはずなんだ。
逆にメタな視点からみてビジービーバー関数の全域性が成り立たないってどういうことだろう
n状態のチューリングマシンは全部で有限個存在し、停止するか停止しないかのどちらかで
あって、停止しないものは除く。停止するチューリングマシンも有限だけ存在するのであれば
出力する値の最大値が存在する。 全域性が成り立つようwell definedに定義されていれば、全域性を証明するのに必要な理論は
定義の中に含まれているということです >>528
怖くてリンク踏めないがn=7910という数値は何に由来するんだろ？ ■■■輝かしい日本の未来の学問は、馬鹿板をしない国民一人一人が作るもの。■■■
￥ >>542
なんかコーネル大学図書館ってサイト
普通の大学機関だと思う ■■■輝かしい日本の未来の学問は、馬鹿板をしない国民一人一人が作るもの。■■■
￥ これって7910状態のビジービーバーの値を特定できないって話ではないのか？
ビジービーバーの存在とは別の話なんじゃないのか？
うーん。 チャイティンのΩも何ビット以上特定しようとすると公理を追加する必要がある
みたいな話はどこかで聞いたことがあるが、それと似たようなもんかなぁ。 ■■■輝かしい日本の未来の学問は、馬鹿板をしない国民一人一人が作るもの。■■■
￥ >>546
>>528の説明であってるんじゃない?
ビジービーバー関数BB(n)のZFCで扱える領域を越えるnの値が大きくても7910
nはテープの長さで、2状態のチューリングマシンだって ■■■輝かしい日本の未来の学問は、馬鹿板をしない国民一人一人が作るもの。■■■
￥ >>549
7910はテープの長さじゃなくて状態数、2は状態じゃなくてテープアルファベットの種類だろ？ ■■■輝かしい日本の未来の学問は、馬鹿板をしない国民一人一人が作るもの。■■■
￥ >>456
"可算無限濃度より大きく、連続体濃度より小さい濃度の個数"をチューリングマシンを用いて求める事は可能なのか？
可能なら（計算量はともかく）一意に決まるだろうし、不可能ならそれはただの「外部変数」なのでは？ ■ このスレッドは過去ログ倉庫に格納されています
