巨大数探索スレッド13

1132人目の素数さん2017/12/08(金) 22:59:03.88ID:8DbvNjq1
大きな実数を探索するスレッドです。

前スレ
 http://rio2016.5ch.net/test/read.cgi/math/1484923121/
巨大数研究室
 http://www.geocities.co.jp/Technopolis/9946/
巨大数 (Wikipedia)
 http://ja.wikipedia.org/wiki/%E5%B7%A8%E5%A4%A7%E6%95%B0
ふぃっしゅっしゅ氏の巨大数論PDFと書籍
 http://gyafun.jp/ln/
たろう氏のまとめ
 http://gyafun.jp/ln/archive/7-571.txt
Dmytro Taranovsky の順序数表記
 http://web.mit.edu/dmytro/www/other/OrdinalNotation.htm
巨大数研究Wiki
 http://ja.googology.wikia.com/wiki/

2132人目の素数さん2017/12/08(金) 23:00:41.37ID:8DbvNjq1
12が終わっていたので立てました

3132人目の素数さん2017/12/08(金) 23:05:50.63ID:FhkUus/o
https://twitter.com/wota1969?t=1&cn=ZmxleGlibGVfcmVjcw%3D%3D&refsrc=email&iid=7ee5dd3e1aad40d9a574c9f18d8e62a1&uid=525178774&nid=244+272699405

4132人目の素数さん2017/12/08(金) 23:53:59.44ID:eHEqmV0D
削除依頼を出しました

5132人目の素数さん2017/12/09(土) 15:50:10.26ID:xkFAdF/c

6132人目の素数さん2017/12/09(土) 19:08:00.43ID:uy54sgE5
耳栓をしたら世界が変わってワロタ

7132人目の素数さん2017/12/09(土) 20:35:37.12ID:p6fMzslQ

8132人目の素数さん2017/12/09(土) 21:21:25.92ID:zJEmLits
俺的文明レベルの定義
文明のレベルはビジービーバー関数の値をどこまで求められるかで測られる。
現在の人類の文明レベルは4

9132人目の素数さん2017/12/10(日) 01:48:55.49ID:nwVYj8m4
囲碁、チェス、将棋のプログラムで一気にトップに出た Google に、
絶大なコンピュターパワーでビジービーバー関数の計算にチャレンジしてほしい

10132人目の素数さん2017/12/10(日) 04:39:30.18ID:ieniCcbp
GIMPSみたいに分散コンピューティングしたいけれどあまりにも知名度が

11132人目の素数さん2017/12/10(日) 04:58:42.71ID:gFQMK9Wr
名前がよくない
いっそ社畜関数って名前にしてしまえばもっと共感を呼ぶ

12132人目の素数さん2017/12/10(日) 12:05:06.92ID:MAwb8jeG
計算量がそのまんまビジービーバー関数レベルで増えていってやばい。
指数関数レベルの増え方とは次元が違う・・・と思ったけどほんとにそうだろうだろうか?

13132人目の素数さん2017/12/10(日) 12:38:10.99ID:MAwb8jeG
停止するプログラムをすべて最後まで走らせてその中で最大の値を求める。
これは本当に最後まで走らせる必要があるわけではない、
どこまで計算効率を上げられるか
停止しないプログラムは停止しないという判定をしなければならない。
限定的に停止性を判定するアルゴリズムは存在するものの、それをどこまで簡単にできるか?
またそのプログラムを開発するプログラムはもっと複雑になるのではないか?
停止性を判定するプログラムはオラクルで与えられてもいい、つまり適当に作ったプログラムが
たまたまそうなっていたとしてもいい、ではそれがほんとうに停止性を判定するプログラムであると
判定するプログラムは?
停止性を判定するプログラムであると判定するプログラムであると判定するプログラムは?

これもうわかんねえな

14132人目の素数さん2017/12/10(日) 14:30:25.03ID:bZV8J1/5
>>13
普通にゲーデルの不完全性定理を停止問題として言い換えられるのぐらい知ってて言ってるよね?。

15132人目の素数さん2017/12/11(月) 03:42:36.57ID:iDlBu66T
BB(100)とかは無理だろうけど、BB(5)とかBB(6)くらいなら、
Googleが頑張ればそのうちなんとか、とか思わないでもない

16132人目の素数さん2017/12/11(月) 13:17:10.60ID:LVWAoDNS
そんな宣伝にならんことに金を使うわけがない

17132人目の素数さん2017/12/11(月) 13:18:30.68ID:LVWAoDNS
実際に求める必要なんてないと思うが
グラハム数だって計算しようなんてヤツはいない

18132人目の素数さん2017/12/11(月) 16:02:38.03ID:KefKcF5V
>>14あくまで限定的な停止性判定のアルゴリズムの話なので。
たとえば4状態のプログラムは有限個しか存在しないので、究極最初からプログラムの中に
それぞれの入力されたプログラムに対する答えを用意しとけば4状態の停止性を判定する
プログラムとなります。

と書いて思ったけどこんなのでもアルゴリズムと言っていいのか? プログラムとは言えるけど

19132人目の素数さん2017/12/11(月) 16:05:57.71ID:KefKcF5V
計算可能レベルの追究が結果的にビジービーバー関数の値を求めることにもなるだろう。
逆も然りだが、こちらからはけっこう難解

20132人目の素数さん2017/12/11(月) 20:10:05.70ID:aAlStgH7
ならないよwww

21132人目の素数さん2017/12/11(月) 20:23:56.81ID:iDlBu66T
実際に求めると言うのは、当然10進数で求めるという意味ではなくて、
優勝マシンを決定すること
その一般的なアルゴリズムはないけど、小さいnに対しては決定できても
おかしくはない

22132人目の素数さん2017/12/11(月) 22:57:22.67ID:KefKcF5V
巨大数ベイクオフ大会もある意味BB(512)の値を追求する大会ですし

23132人目の素数さん2017/12/12(火) 08:24:50.60ID:TStY9q2s
>>21
それを追求しても巨大数探索にはならんぞ

24132人目の素数さん2017/12/12(火) 09:12:47.35ID:2YwkEi3X
前スレでビジービーバー関数の全域性うんぬん言ってたやつに致命的な間違いを見つけた。
ω矛盾の定義がおかしい。∃n∈(自然数)(Q(n))が証明可能なのに
Q(0),Q(1),Q(2),...がいずれも証明不能であることをω矛盾の定義といってたが、
これだとペアノ算術に例えば定数記号aを加えただけの拡張でも、
a = a から ∃n (a = n)が導出できる一方で、a = 0,a = 1,a = 2,... のいずれも証明不能で、
ω矛盾になる。しかし、これにa = 0という仮定を加えても無矛盾だから、
超準モデルになるとは限らない。

間違いの源はおそらく日本語版wikipediaだ。

"ω矛盾とは、自然数 n によって定まる論理式 Q(n) が存在して、次を満たすことをいう。
Q(0), Q(1), Q(2), …が全て証明可能であるが、「∃n: ¬Q(n) 」も証明可能である"

この記述は正しい。問題があるのはその下の、

"公理系が無矛盾であれば、対偶を取る事により、ω矛盾の概念が次と同値である事を示せる:
「∃n: Q(n) 」が証明可能であるが、Q(0), Q(1), Q(2), … のいずれも証明可能ではない。"

というところだ。最初の記述は「Q(0),Q(1),Q(2),...が証明可能で、かつ∃n(¬Q(n))も証明可能」
と言い換えられる。すると、実はAならばBの形になってないから、そもそも"対偶を取る"のは変だ。
英語版wikipediaには下の記述に該当する文は無い。
同値でないことも簡単に確認できる。ペアノ算術に定数記号aを加えただけの拡張は、
∃n(a = n)が証明可能で、a = 0, a = 1, ...が証明不能なことから下の記述を満たすが、
∃n(¬(a ≠ n))が証明可能な一方、a ≠ 0, a ≠ 1, ...は証明不能だから、上の記述を満たさない。
よって2つの記述は同値でない。
だから、前スレのあの証明では、「ビジービーバー関数の出力が超準的自然数になる」ことは
証明できていない、と言える。

あー、すっきりした

25132人目の素数さん2017/12/12(火) 18:38:09.54ID:2YwkEi3X
まぁでも、「ビジービーバー関数の出力が超準的自然数になる」、すなわち
BB(x)をビジービーバー関数として、
「十分大きな自然数Mについて、0 < BB(M), 1 < BB(M), 2 < BB(M), ...が証明可能」
は証明できてないけど、もっと弱い主張である※ならば簡単に証明できる。
(∀n(n < BB(M))と、0 < BB(M), 1 < BB(M), ...は異なる。∀n (n < BB(M))からは、
例えばBB(M) + 1 < BB(M) を導出できるので明らかに矛盾)

※: 任意の無矛盾かつ帰納的公理化可能な公理について、ある自然数Mが存在して、
任意のn ∈ {0,1,2,...}について公理に n < BB(M) という式を加えてもなお無矛盾

やや分かりにくいけど、公理に0 < BB(M)とか1 < BB(M)とか 2 < BB(M)をいくら加えても
そこから矛盾が導出できない、ということ。ビジービーバー関数を扱える公理じゃないと
いけないので、多分自然数論を含むだろう。

26132人目の素数さん2017/12/12(火) 19:44:25.84ID:2YwkEi3X
証明: 背理法による。どんなに大きな自然数Mに対しても、n < BB(M)を仮定すると矛盾が
導出できるような n ∈ {0,1,2,...}が存在すると仮定する。
公理が帰納的公理化可能なので、以下のような計算機械を構成すれば、必ず停止する

k = 0 とする
親プロセス:
(1).子プロセスに k < BB(M)を与えて起動する
(2).子プロセスが1つでも停止したら(3)へ
そうでなければ k を 1 増やして(1)へ戻る
子プロセス:
k < BB(M)が与えられたら公理 + (k < BB(M))から
矛盾の導出を試みて、矛盾を導出したらkを出力して停止
また、親プロセスが停止したら停止
すべてのプロセスは並行して行われる

この計算機械の出力する値を N とすると、N < BB(M)から矛盾を導出したので
N ≧ BB(M)を導出でき、状態数M以下のチューリングマシンをエミュレートして
N個を超える1を出力した時点でそのチューリングマシンは停止しないと判定できる。
どんなに大きな自然数Mに対してもこのことが言えるので、
任意の停止性問題を解ける計算機械が構成できることになり矛盾する。

よって背理法より※が示された。

27132人目の素数さん2017/12/12(火) 20:36:45.94ID:2YwkEi3X
※からは面白いことが分かる。
例えば、いかに大きなn∈{0,1,2,...}についてもn < BB(M)の仮定と矛盾しないということは
ある程度大きなMについてBB(M)に意味のある上限を導出できないことを意味する。
上限 m∈{0,1,2,...} が導出できるなら、m < BB(M)の仮定を加えると矛盾し、※に反するから。
(ここでいう意味のない上限とは、BB(M) < BB(M) + 1など)

ある程度大きなというのがどれくらいかは公理によるが、例えばZFCで100とすると
BB(100)の上限がふぃっしゅ数ver6ぐらい、とか、H(ψ(Ω_ω))である、といった
何かしら計算可能なもので表せると証明されることはありえない、ということになる。

あとは、"公理が無矛盾 ⇒ 公理 + (n < BB(M)) が無矛盾"は示した通りだが
逆は明らかなので公理と公理 + (n < BB(M))は無矛盾性同値でもある。

なんだか、まるでBB(M)は連続体濃度みたいな感じがする。
連続体濃度cも、ZFC + (アレフ1 < c) とか ZFC + (アレフ2 < c),...にしたって無矛盾だし、
cは存在するし一定の濃度でもあるはずだけど、可算無限との間にいくつの濃度の異なる集合が
あるのか決まらない、といったような。
何をもって一意に定まるとするのかは、もはや哲学の問題だね。

28132人目の素数さん2017/12/12(火) 21:22:07.48ID:TStY9q2s
いまだにビジービーバーみたいな小さな関数で思考が止まってるのか

29132人目の素数さん2017/12/12(火) 21:22:23.17ID:TStY9q2s
進歩がないねえ

30132人目の素数さん2017/12/12(火) 21:25:21.22ID:TStY9q2s
グラハム数が指数の塔で表現出来なくても
ちゃんと大きさが見積もれる

31132人目の素数さん2017/12/12(火) 21:53:39.39ID:Lg1Qpa+v
計算可能レベルを全否定ですか?

32132人目の素数さん2017/12/12(火) 23:20:33.49ID:mvyOcewj
嫌味ったらしい。何様だよ

33132人目の素数さん2017/12/12(火) 23:23:03.05ID:dr4XG1HO
ビジービーバーは神聖にて不可侵なものです。

34132人目の素数さん2017/12/12(火) 23:47:22.18ID:Lg1Qpa+v
前スレの「フワフワした感じがすっきりしないんじゃないか?」を「大きさを見積もることができない」
と言っていると勘違いされた可能性はどうだろう

35132人目の素数さん2017/12/13(水) 06:28:12.09ID:INqifKwb
>>26
「どんなに大きな自然数Mに対しても、n < BB(M)を仮定すると矛盾が
導出できるような n ∈ {0,1,2,...}が存在する」
としたら、「1をn個出力するまでチューリングマシンを走らせる」とするだけで
停止性問題が解決してしまうので、そういうnが存在しないということが
停止性問題と同値であることは自明

36132人目の素数さん2017/12/13(水) 07:03:06.15ID:Tekttjs5
>>31
小さな数しか作れないものは否定されてもしょうがない

37132人目の素数さん2017/12/13(水) 09:37:19.32ID:Zm7XTPvZ
無限の無限乗の無限乗の無限乗の無限乗の・・・・・(これが無限に続く)

ってどのくらい大きいの?

38132人目の素数さん2017/12/13(水) 09:48:50.30ID:gNGMfg74
>>37
「無限」じゃないですかね
元の無限とは異なるんだろうけど

39132人目の素数さん2017/12/13(水) 11:38:16.69ID:gNGMfg74
無限について考えていてふと思ったんだけど、仮に「ゼロで割る」という操作が「できる」と仮定したら、何かおもしろいことが起きるか、
例えば、u×0=1という関係が成り立つuを仮定して、これをあたかも虚数単位のようにして数を拡張すること、
具体的には、実数集合Rに対して、このuを使って集合U={a+bu|a、b∈R}を定義することができるが、このような集合Uに、果たして数学的な意義はあるのか
それともまったく無意味なのか

こんなことを思い付いて研究してる数学者が、じつは既に居るんじゃないかって気がしてるんですが、その辺りどうなんでしょうか?

40132人目の素数さん2017/12/13(水) 12:01:20.58ID:r64hvitv
とりあえずルベーグ測度を勉強すれば幸せになれると思う

41132人目の素数さん2017/12/13(水) 12:16:49.85ID:mq6hIL5p
計算可能レベルは別スレ立てるといいかもしれない

42132人目の素数さん2017/12/13(水) 13:07:40.65ID:HhXxkefZ
>>41
だね

43132人目の素数さん2017/12/13(水) 13:08:41.64ID:HhXxkefZ
>>39
とりあえず、ある程度までは自力で考えてみよう

44132人目の素数さん2017/12/13(水) 13:20:01.86ID:2FmXVCa9
1/0と0/0を割と自然に追加したのが車輪
でも
(1/0)*0
は1じゃなく0/0になっちゃうが

45132人目の素数さん2017/12/13(水) 18:51:22.26ID:iZ+rAmTJ
結局、巨大数を求めるにあたってどこまで奇妙な性質をもつことを許容できるか
という哲学の問題なのかな。

いったんここでは自然数論のモデルに属しうるものはすべて自然数と呼ぶことに
して、以下の4つに分類しよう。特に断りがない場合、証明可能とは古典論理の
もとで証明可能であることを意味する。

(1)存在を直観主義論理のもとでも証明可能な自然数

例: ふぃっしゅ数ver6など、計算可能な手段で求められるもの

(2)存在を証明可能だが、直観主義論理のもとでは証明不能な自然数

例: ある程度大きな入力に対するビジービーバー関数やラヨ関数、
その他の計算不能関数の出力?

(2)の数は、さっきの※みたいな、任意のn∈{0,1,2,...}についてnより大きい
としても無矛盾、といったやや奇妙な性質をもつようになると思われる。

続く

46132人目の素数さん2017/12/13(水) 20:09:06.97ID:iZ+rAmTJ
(3)存在を仮定するとω矛盾であることが導ける、したがって自然数論からは
おそらく存在が証明不能であるが、無矛盾性は強くしない自然数

おそらく、としたのは自然数論が矛盾していれば何でも証明可能であるため。

例: 「自然数論の矛盾の導出を試みて、導出したら停止する計算機械」
が停止するまでにかかるステップ数

自然数論 + (自然数論は矛盾)という公理を採用すれば停止することを証明可能で、
自然数論が無矛盾ならば(自然数論は無矛盾)は導出できないため、
自然数論が無矛盾ならば、自然数論 + (自然数論は矛盾)もまた無矛盾
よって無矛盾性は強くなっていない。

(4)存在を仮定すると、ω矛盾になるうえ、無矛盾性も強くなるが、
矛盾はしないような自然数

集合論では、大きすぎて存在を仮定すると無矛盾性が強くなるような
濃度のことを巨大基数と呼ぶのだった。いわば、(4)は自然数論版の
巨大基数である。ただしこれについての研究はほとんど無いから、
具体例を挙げるのは難しい。

(3),(4)に属する自然数は超準数で、したがって(1),(2)に属するどの自然数よりも大きい。
(1),(2)は存在を証明できる自然数で、(3),(4)は存在しないとは証明できない自然数である。
(4)に属する自然数はおそらく(3)に属する自然数よりも大きい。

47132人目の素数さん2017/12/13(水) 20:17:08.41ID:iZ+rAmTJ
ちなみに>>39にあるような u * 0 = 1となるuについては、実数0は加法の単位元で、
実数1は乗法の単位元なので、1 + 0 = 1と分配法則から
u = u * 1 = u * (1 + 0) = u * 1 + u * 0 = u + 1
よって u = u + 1 両辺からuを引いて 0 = 1 実数の0と1は等しくないので矛盾
だからこのような u は、(1)から(4)のどれにも属さない、
存在を仮定すると矛盾が導ける数、ということになる。

48132人目の素数さん2017/12/13(水) 22:50:14.62ID:iZ+rAmTJ
あっ、そうだ。
>>39
さすがに0の逆数っていうのは先述の通り矛盾するからないけど、
どんな実数よりも大きい超実数という数の存在を仮定して色々する
超準解析っていうのがあるよ。

49132人目の素数さん2017/12/13(水) 23:29:01.97ID:gNGMfg74
>>47
通常の算術が成り立たなくなることは理解しました。ありがとうございます。
スレチってこともあるのであまり深くは掘り下げないことにします。
そういえばu=u+1って式はuが可算集合濃度だと成立する式ですね。この場合は辺々uを引く操作に意味がないわけですが。

50132人目の素数さん2017/12/13(水) 23:30:52.41ID:Tekttjs5
>>45
ビジービーバー関数が存在することに疑問の余地がある?

51132人目の素数さん2017/12/13(水) 23:33:28.79ID:Tekttjs5
>>45
ビジービーバー関数の何が証明不可能だと言ってる?
Σ(9^9^9)が明確に定義されていて存在することは明らかだよね?

52132人目の素数さん2017/12/13(水) 23:45:13.01ID:Tekttjs5
少なくとも、存在することが証明できる数でないと探索にならないのでは?

到達不可能基数のような、巨大基数を仮定すると定義できる巨大自然数
みたいなのがあるの?
関数であればそういう物もあるような気がするけど、
単なる1個の自然数にそういうのがある?
自然数に計算可能も計算不可能も無いよね?

53132人目の素数さん2017/12/13(水) 23:48:18.54ID:r64hvitv
スレを計算可能レベルと不可能レベルに別けるのは構わないっちゃあ構わないけど、
不可能レベルだけでそんなに話題があるだろうか? と思って前スレみてみたらそこそこあるな

54132人目の素数さん2017/12/13(水) 23:57:54.92ID:r64hvitv
>>24からどうも引っかかるので整理

"ω矛盾とは、自然数 n によって定まる論理式 Q(n) が存在して、次を満たすことをいう。
Q(0), Q(1), Q(2), …が全て証明可能であるが、「∃n: ¬Q(n) 」も証明可能である"

これは正しい

"公理系が無矛盾であれば、対偶を取る事により、ω矛盾の概念が次と同値である事を示せる:
「∃n: Q(n) 」が証明可能であるが、Q(0), Q(1), Q(2), … のいずれも証明可能ではない。"

これは確かにおかしいと思う、Q(0), Q(1), Q(2), … のいずれも証明可能ではないというのは統語論的に
決定できないと言うだけで、Q(0), Q(1), Q(2), … のいずれも反証可能ということではないので

55132人目の素数さん2017/12/14(木) 03:21:49.88ID:ba2R7XSw
スレの統一ルールはないので、計算可能でも不可能でも、自分が好きな話題を出せばいい

56132人目の素数さん2017/12/14(木) 03:25:27.76ID:ba2R7XSw
数年に1スレ消費するような閑散としたスレッドで、前スレは久々に1年以内に消費した
程度なんだから、話題なんてごった煮でよくて、巨大数に関することは基本的になんでもあり

57132人目の素数さん2017/12/14(木) 18:51:13.15ID:OUBB90zM
公理 A に対して、※を満たすくらい十分に大きな定数 M を用意して、
A に可算無限個の式を加えた以下のような公理
A + (0 < BB(M)) + (1 < BB(M)) + (2 < BB(M)) + ...
を A* として、コンパクト性定理より A が無矛盾なら A* も無矛盾
A から ∃n (n = BB(M)) を証明可能とすると、 A のモデルはすべて
BB(M)に該当する数を含む。 一方で A* のモデルではBB(M)は必ず
超準数である。A* が A を含むから、A* のモデルは A のモデルでもあり、
したがって採用する A のモデルによってはBB(M)は超準数になる。
さらに A がω無矛盾であるとすると、 A のモデルには標準モデルもあるため、
採用する A のモデルによってはBB(M)は標準数∈{0,1,2,...}になる。
したがってBB(M)の値はモデルの選び方に依存して変わる。

f が自然数上の計算可能関数とすると、n∈{0,1,2,...}について
0 = f(n), 1 = f(n), 2 = f(n), ...のうちのいずれかは証明可能である。
証明可能な式はどんなモデルを採用しても真なので、標準数を入力したときの
計算可能関数の出力する値はモデルの選び方に依存しない。
当然、0 = BB(M), 1 = BB(M), 2 = BB(M), ...のうちのいずれも証明不能である。
これは、任意の n∈{0,1,2,...} について n < BB(M) としても無矛盾である
ことによる。(n < BB(M) ならば n ≠ BB(M)である)

さっきは暗黙的に標準モデルで考えたために(2)の具体例が(3)の具体例
よりも小さいって言ったけど、超準モデルの中にあるBB(M)だったら
(3)の具体例を超えることも十分に考えられるな。

58132人目の素数さん2017/12/14(木) 18:59:44.90ID:SmK0uiXp
一年後にはここに書いてあること全部理解したい

59132人目の素数さん2017/12/14(木) 20:35:31.66ID:uaaeAmZt
順序数や基数は整列集合だから
○○を満たす最小
みたいなのがあるわけで

整数だと
nが○○を満たせばn-1も満たすから
そういう形で大きな数を定義するのは無理では?

60132人目の素数さん2017/12/14(木) 20:42:18.13ID:uaaeAmZt
>>57
公理系によってBBの値は変わらんよ

公理系で証明可能だろうが不可能だろうが
BBの値に影響無い
単に選んだ公理系に証明の能力が無いだけ

61132人目の素数さん2017/12/14(木) 20:43:56.64ID:uaaeAmZt
選んだ公理でマシンの動きが変わるなんて事はあり得ない

62132人目の素数さん2017/12/14(木) 21:09:09.43ID:uaaeAmZt
BB(M)の大きさを語るのに
その大きさをまともに扱えない公理系を使うのが間違い

幼稚園児がBB(4)=14の矛盾を導けないからといって
BB(4)=14と教えれば幼稚園児にとってはBB(4)=14である

と言ってるようなもの

63132人目の素数さん2017/12/14(木) 21:19:41.01ID:uaaeAmZt
計算可能な関数も
公理によって値を返すかどうか証明不可能なものがあったと思うけど

64132人目の素数さん2017/12/14(木) 21:58:06.67ID:9TwIcPNq
公理系の強さが順序数で表されるというのは興味深い。
深く勉強してみたいものだ。

65132人目の素数さん2017/12/14(木) 22:21:38.42ID:a1kx2fsY
1月発売の数セミが外史特集

66132人目の素数さん2017/12/15(金) 00:48:21.45ID:gG6rttTC
二階部分を量化して任意の部分集合は最小値をもつと言えば自然数論の超準モデルと区別できるようになる

67132人目の素数さん2017/12/15(金) 13:16:52.80ID:CF3vb9NM
>>64
公理系の強さは全順序じゃないけど

68132人目の素数さん2017/12/15(金) 18:42:15.17ID:0zA6t2JR
>>62
少なくともZFCにおいては、BB(4) = 13 が証明されているから、
ZFCのもとで 4 は※をみたすほど大きな数ではない。
無数にある無矛盾な公理系のうちどれを採用すべきかは数学の範囲内
じゃ答えられないし、ある公理がもつ無数のモデルのうちのどのモデル
を採用すべきかも数学の範囲内じゃ答えられない。
しかも、ビジービーバー関数の出力をすべて決定できる無矛盾な公理は必ず
帰納的公理化不能になるから、そんな公理の採用を強制されても神様にしか
扱いきれない。
数学の範囲内で答えられないなら哲学の出番になるけど、俺は哲学的議論
なんてしたくない。決着がつくことはほとんどありえないからだ。
俺はそんな哲学的議論をするより、あくまで数学の範囲内で、
そして人間が扱える公理の範囲内で、考察対象がもつ性質について
述べる方がずっと面白いと思う。

69132人目の素数さん2017/12/15(金) 20:02:31.79ID:yReWMSiw
BB(M)が扱える公理系ならどの公理系を選んでも値は同じ
どの公理系を選ぶかなんて考える必要は無い

その辺はBB(4)となんら変わらない

70132人目の素数さん2017/12/15(金) 20:12:48.76ID:yReWMSiw
定義自体は非常に簡単

71132人目の素数さん2017/12/15(金) 20:22:15.10ID:yReWMSiw
大きい数を競うのに、
実際に値を求める必要は全くなくて、
大小を比較する手段があれば十分

72132人目の素数さん2017/12/15(金) 21:49:38.87ID:mHxNdm4K
どんな公理を選んでも「決定できない」ものを「定義された」とみなすかどうかの話。
定義できたとみなしたときに、それを「チューリングジャンプ」とか「神託機械によって
計算された」と表現するので、計算可能性理論の領域に入ってくる。

73132人目の素数さん2017/12/15(金) 22:28:52.18ID:gG6rttTC
>>25
>「十分大きな自然数Mについて、0 < BB(M), 1 < BB(M), 2 < BB(M), ...が証明可能」
>は証明できてないけど、もっと弱い主張である※ならば簡単に証明できる。

これがおかしい。ビジービーバー関数はFOSTで記述可能、
よって1階述語論理の完全性により、任意の自然数nにつきあるaがただひとつ存在し、BB(n)=aを
証明可能

74132人目の素数さん2017/12/15(金) 22:33:27.27ID:gG6rttTC
超準モデルは>>66で否定できる。よってビジービーバー関数の値が超準的自然数にならないように
定義することもできる、というかそういう定義だよな?

75132人目の素数さん2017/12/16(土) 04:23:58.74ID:zeGJu5wf
P(n)はn番目の素数
(sin(1/2)+sin(1/3)+sin(1/5)+sin(1/7)+sin(1/11)+sin(1/13)+・・・+sin(1/P(n)))^2+(1+cos(1/2)+cos(1/3)+cos(1/5)+cos(1/7)+cos(1/11)+cos(1/13)+・・・+cos(1/P(n)))^2≒(n+1)^2

76132人目の素数さん2017/12/16(土) 11:18:04.65ID:qKav/W7S
>>66 もっと詳しく。urlでもいい。
>>69 公理とモデルごっちゃにしてない?
>>73 >>25は別に∃a(BB(n)=a)が証明不能とは言ってない。
BB(n)=0,BB(n)=1,...の内のいずれも証明不能なのは>>57の通り>>25の※から導けるけど。

77132人目の素数さん2017/12/16(土) 12:52:27.54ID:Es/6tyQF
そろそろスレチだ

78132人目の素数さん2017/12/16(土) 12:55:59.67ID:Es/6tyQF
https://ja.m.wikipedia.org/wiki/%E3%83%93%E3%82%B8%E3%83%BC%E3%83%93%E3%83%BC%E3%83%90%E3%83%BC

ビジービーバー関数がちゃんと定義できてないなんて言ってるのは>>76だけ

79132人目の素数さん2017/12/16(土) 13:30:05.26ID:gmpfSCpV
>>76
∃a(BB(n)=a)ではなくBB(n)=aが証明可能、つまりBB(n)=0,BB(n)=1,...の内のいずかが証明可能
であり※は誤り、という主張です

80132人目の素数さん2017/12/16(土) 13:45:05.46ID:gmpfSCpV
>>26はMがどこまでも大きくなればBB(M)もどこまでも大きくなる、ということを証明しているんじゃ? あと

>N個を超える1を出力した時点でそのチューリングマシンは停止しないと判定できる。

N個を超える1を出力した後にその1を消して停止することも考えられるのではないでしょうか?

81132人目の素数さん2017/12/16(土) 14:25:13.18ID:gmpfSCpV
>Mがどこまでも大きくなればBB(M)もどこまでも大きくなる、ということを証明しているんじゃ?

これはこちらの勘違いでした、スマン

82132人目の素数さん2017/12/16(土) 15:51:25.46ID:uVM5P2Vx
>>79
BB(n) = 0, BB(n) = 1, ...のいずれかが(帰納的公理化可能な公理から)証明可能なら、
>>26と似たような計算機械、すなわち
BB(n) = 0の証明を試みる子プロセス、BB(n) = 1の証明を試みる子プロセス、...
を次々生成する親プロセスを作り、子プロセスが一個でも証明完了すれば
得られたBB(n)を出力して全プロセスを終了、とすれば子プロセスの1つは証明完了
することは確実なので、BB(n)を計算できる機械が作れ、BB(n)の計算不能性と矛盾

83132人目の素数さん2017/12/16(土) 16:32:01.68ID:uVM5P2Vx
>>80
優勝者よりも多くの1を書きながらそれを消して停止するマシンの存在は
確かにありそうで、その点で>>26には問題があるけど、
「N個を超える」のところは「N*2個」とか「N^2個」、はたまた「2^N個」
「Ackをアッカーマン関数としてAck(N, N)個」と置き換えても停止性問題を
解ける機械が作れるという結論に変わりなく、わざわざAck(N, N)個以上書いた1を
N個未満になるまで消してから停止するマシンがあるのに優勝マシンにはたったの
N個しかテープに1が無い、っていうのは(証明はしてないが)考えにくい。
だから結論は疑っていない。

84132人目の素数さん2017/12/16(土) 17:06:04.26ID:uVM5P2Vx
あ、テープにある1の総数は増やさないけど停止しないものもあるじゃん。
例えば0を読み取ったら状態も文字も変えずただ右にシフトするだけだったら、
空のテープをずっと右に行くだけで停止しないのに1の数は0個のままだから
停止しないと判定されることもない。
>>26 はまずいな... ビジービーバー関数じゃなくて最大ステップ数関数に
譲歩したほうがより安全か。

85132人目の素数さん2017/12/16(土) 18:36:31.02ID:1A9y1fOT
>>26については>>35でおしまいじゃないの?
どこまで計算しても「計算がいずれは終了するのか永遠に終了しないのかを判定する
一般的アルゴリズムは存在しない」ことが停止性問題。最大値を確実に見積もれたら、
その最大値まで計算すれば判定ができてしまうので停止性問題が解決してしまう。
つまり、>>26の仮定がおかしいということ。

86132人目の素数さん2017/12/16(土) 19:31:17.51ID:uVM5P2Vx
まあ背理法で示す訳だから矛盾を導くためのおかしい仮定をするのは当然だが、
>>35では>>84の例で出した1を出力しないのに停止しないマシンには対処できてない。
いましがた、詳細は省くが、任意のn状態数チューリングマシンに対して、
少なくとも21n状態数チューリングマシンなら1ステップごとに1の数が少なくとも1つは
増えていく、つまりステップ数を数えながら動くマシンを作れることが分かった。
これより、最大ステップ数関数S(n)
= "n状態数チューリングマシンが停止するまでにかかるステップ数の最大値+1"
とすれば、 BB(n) ≦ S(n) ≦ BB(21n) となる。
あとは>>26を改造して n ≧ S(M)が導けたときに n ステップまで動かせば停止性問題解消、
とすれば、あるMが存在し 0 < BB(21M), 1 < BB(21M), ...を加えても無矛盾と言える
ので、∀n (BB(n) < BB(n+1))から、結局は※と同じことを導出できるな。

87132人目の素数さん2017/12/16(土) 22:46:14.10ID:qKav/W7S
>>66の任意の部分集合が最小値をもつのと、
超準モデルを否定できるのとのつながりが分からない。

88132人目の素数さん2017/12/17(日) 00:32:50.97ID:AtDSd9G4
>>26
子プロセスの「矛盾を導出する」のはチューリングマシンと同じ能力の計算機械で出来るの?

89132人目の素数さん2017/12/17(日) 01:50:02.89ID:I7x5AqJ7
停止性問題は任意のチューリングマシンの停止性を判定するアルゴリズムは存在しないというだけで
特定のチューリングマシンの停止性を判定できても矛盾はない・・・よな

超準モデルは必ず無限下降列をもってたと思う

90132人目の素数さん2017/12/17(日) 01:56:49.18ID:I7x5AqJ7
それぞれのMにつき、状態数Mのチューリングマシンの停止性を判定するチューリングマシンが
それぞれに存在するだけなら停止性問題に触れない

91132人目の素数さん2017/12/17(日) 04:20:26.30ID:hGoCNWLo
>>86
なるほど。「詳細は省くが」のところが、けっこうすごいことやったのでは?

92132人目の素数さん2017/12/17(日) 09:56:47.49ID:9SSnit6T
>>88
一階述語論理の健全性と完全性より証明可能⇔恒真
帰納的公理化可能な公理から証明可能な式は枚挙可能
よって証明可能な式を枚挙していれば必ず恒真な式は証明される
>>89
ZFCの無限公理が存在を保証する集合をNとして、ZFCが無矛盾なら、
ZFCに定数記号 v を加え、ZFCに v ∈ N という式を加えても無矛盾
{} ∈ v, {{}} ∈ v, {{}, {{}}} ∈ v , ...の式を有限個加えても無矛盾
よってコンパクト性定理より、
ZFC + (v ∈ N) + ({} ∈ v) + ({{}} ∈ v) + ({{}, {{}}} ∈ v) + ...もまた無矛盾
これをZFC*とすれば、ZFC*のモデルはZFCのモデルでもあるが、超準モデルである。
ZFC*は正則性公理を含むので、ZFC*のモデルの中の集合は∈の無限降下列を持たない。
よって無限降下列が有無を根拠に超準モデルを排除できる訳ではない。
この事実をあえて解釈するなら、超準モデルの中では超準数は有限にしか見えない、
だから自分が超準モデルの中にいるのか標準モデルの中にいるのか分からない、
といったところか。

93132人目の素数さん2017/12/17(日) 10:22:52.46ID:9SSnit6T
>>90
自然数Mを入力として与えれば、論理式 n < BB(M)の構成自体は計算可能な手段
で出来るから、 >>26の計算機械は任意のMを入力にとることができる。
だから任意のチューリングマシンの停止性を判定できる一つの計算機械になって矛盾を導ける。
>>91
そんなに気になるか〜。仕方がない。省いた部分を書いてあげる。
テープを 3k, 3k + 1, 3k + 2 番目のセルの3つに分割して、
3k 番目のセルはエミュレート用に、3k + 1, 3k + 2 番目のセルはステップ数の
カウントと制御用に使う。
n状態数マシンのエミュレートを行い、エミュレータが
1ステップ進むたびそこのセルの1つ右と2つ右のセルに合わせて10と書いて、
そこがエミュレータの現在のヘッドの場所だと示す。そして右に進み、3k + 1, 3k + 2
番目のセルが合わせて00になってるところを見つけたら01にして左に戻り、10の
エミュレータの現在ヘッド位置まで戻りエミュレートを再開する。
このようなマシンの構成のために、まずエミュレート用の状態数n個を用意して、
エミュレータのヘッドの状態と読み取った文字(0 or 1)を記憶するための状態として
2n個、今いるセルがエミュレータのヘッド位置から右に 1, 2, 3k, 3k + 1, 3k + 2番目
なのかを記憶するため2n個の5倍、そして往路なのか復路なのかを記憶するのにさらに2倍
よって n + n * 2 * 5 * 2 = 21n 個の状態数があれば足りる。
省いた理由が分かってくれるとうれしいな。

94132人目の素数さん2017/12/17(日) 10:33:10.44ID:9SSnit6T
さて、書きたいことは書いたし、もうスレからおいとまするか。
あ、巨大数探索スレだから一つ巨大数を提示してからにしよう。
X = "「自然数論から矛盾の導出を試みて導出したら停止する計算機械」が
停止するまでにかかるステップ数"

自然数論が無矛盾ならXの存在を証明できないし、ゲーデルの不完全性定理より
Xの存在の否定も証明できない。
そして、任意の n ∈ {0, 1, 2, ...}について、 n < X が証明可能、すなわち
0 < X, 1 < X, 2 < X, ... がいずれも証明可能である。
これを巨大数と認めるかどうかは哲学の問題だから俺は言及しない。

95132人目の素数さん2017/12/17(日) 11:45:14.13ID:fCl1boMi
>>94
定義が曖昧過ぎませんかねえ
哲学とか言う前に

96132人目の素数さん2017/12/17(日) 11:49:34.78ID:fCl1boMi
>>91
別にそこはどうでも良いよ
21倍も状態を持てば押さえ込むのは簡単だし

そんなことをしなくとも
シフト関数と大差ないわけだし

97132人目の素数さん2017/12/17(日) 12:38:16.78ID:fCl1boMi
自然数論が無矛盾なら停止しない
矛盾していれば停止する

無矛盾を前提にすると停止しないので値は存在しない

98132人目の素数さん2017/12/17(日) 15:02:03.84ID:I7x5AqJ7
任意の超準数uにつき、0でない限りひとつ前の数が存在するのでu-1が存在する。
u-1も超準数である。
以下u-2,u-3,・・・とつづき無限下降列となる

コンパクト性と相いれないのは変だな、自分がどっかで何かを勘違いなり間違いなりしてるんだろう

99132人目の素数さん2017/12/17(日) 15:08:07.97ID:I7x5AqJ7
任意のチューリングマシンは有限時間で停止するかしないかのどちらか
有限個のチューリングマシンの中には有限時間で停止するチューリングマシンが有限個存在する。
有限時間で停止するチューリングマシンの出力する情報の容量なり停止するまでのステップ数なりは有限
有限個の値の中には最大値が存在する。

ビジービーバー関数がこれ以上公理を仮定する必要が無くwell-definedであり、
普通の自然数を返すこと自体は明らかじゃないか?

100132人目の素数さん2017/12/17(日) 15:23:23.46ID:I7x5AqJ7
根本的にビジービーバー関数が定義で標準モデルを指定してないと考えてること自体が間違いかもしらん。

新着レスの表示
レスを投稿する