巨大数探索スレッド13
■ このスレッドは過去ログ倉庫に格納されています
>>13
普通にゲーデルの不完全性定理を停止問題として言い換えられるのぐらい知ってて言ってるよね？。 BB(100)とかは無理だろうけど、BB(5)とかBB(6)くらいなら、
Googleが頑張ればそのうちなんとか、とか思わないでもない 実際に求める必要なんてないと思うが
グラハム数だって計算しようなんてヤツはいない >>14あくまで限定的な停止性判定のアルゴリズムの話なので。
たとえば4状態のプログラムは有限個しか存在しないので、究極最初からプログラムの中に
それぞれの入力されたプログラムに対する答えを用意しとけば4状態の停止性を判定する
プログラムとなります。
と書いて思ったけどこんなのでもアルゴリズムと言っていいのか？ プログラムとは言えるけど 計算可能レベルの追究が結果的にビジービーバー関数の値を求めることにもなるだろう。
逆も然りだが、こちらからはけっこう難解 実際に求めると言うのは、当然10進数で求めるという意味ではなくて、
優勝マシンを決定すること
その一般的なアルゴリズムはないけど、小さいnに対しては決定できても
おかしくはない 巨大数ベイクオフ大会もある意味BB(512)の値を追求する大会ですし 前スレでビジービーバー関数の全域性うんぬん言ってたやつに致命的な間違いを見つけた。
ω矛盾の定義がおかしい。∃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つの記述は同値でない。
だから、前スレのあの証明では、「ビジービーバー関数の出力が超準的自然数になる」ことは
証明できていない、と言える。
あー、すっきりした まぁでも、「ビジービーバー関数の出力が超準的自然数になる」、すなわち
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)をいくら加えても
そこから矛盾が導出できない、ということ。ビジービーバー関数を扱える公理じゃないと
いけないので、多分自然数論を含むだろう。 証明: 背理法による。どんなに大きな自然数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に対してもこのことが言えるので、
任意の停止性問題を解ける計算機械が構成できることになり矛盾する。
よって背理法より※が示された。 ※からは面白いことが分かる。
例えば、いかに大きな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は存在するし一定の濃度でもあるはずだけど、可算無限との間にいくつの濃度の異なる集合が
あるのか決まらない、といったような。
何をもって一意に定まるとするのかは、もはや哲学の問題だね。 いまだにビジービーバーみたいな小さな関数で思考が止まってるのか グラハム数が指数の塔で表現出来なくても
ちゃんと大きさが見積もれる 前スレの「フワフワした感じがすっきりしないんじゃないか？」を「大きさを見積もることができない」
と言っていると勘違いされた可能性はどうだろう >>26
「どんなに大きな自然数Mに対しても、n < BB(M)を仮定すると矛盾が
導出できるような n ∈ {0,1,2,...}が存在する」
としたら、「1をn個出力するまでチューリングマシンを走らせる」とするだけで
停止性問題が解決してしまうので、そういうnが存在しないということが
停止性問題と同値であることは自明 >>31
小さな数しか作れないものは否定されてもしょうがない 無限の無限乗の無限乗の無限乗の無限乗の・・・・・（これが無限に続く）
ってどのくらい大きいの？ >>37
「無限」じゃないですかね
元の無限とは異なるんだろうけど 無限について考えていてふと思ったんだけど、仮に「ゼロで割る」という操作が「できる」と仮定したら、何かおもしろいことが起きるか、
例えば、ｕ×０＝１という関係が成り立つｕを仮定して、これをあたかも虚数単位のようにして数を拡張すること、
具体的には、実数集合Ｒに対して、このｕを使って集合Ｕ＝{ａ＋ｂｕ|ａ、ｂ∈Ｒ}を定義することができるが、このような集合Ｕに、果たして数学的な意義はあるのか
それともまったく無意味なのか
こんなことを思い付いて研究してる数学者が、じつは既に居るんじゃないかって気がしてるんですが、その辺りどうなんでしょうか？ とりあえずルベーグ測度を勉強すれば幸せになれると思う >>39
とりあえず、ある程度までは自力で考えてみよう 1/0と0/0を割と自然に追加したのが車輪
でも
(1/0)*0
は1じゃなく0/0になっちゃうが 結局、巨大数を求めるにあたってどこまで奇妙な性質をもつことを許容できるか
という哲学の問題なのかな。
いったんここでは自然数論のモデルに属しうるものはすべて自然数と呼ぶことに
して、以下の4つに分類しよう。特に断りがない場合、証明可能とは古典論理の
もとで証明可能であることを意味する。
(1)存在を直観主義論理のもとでも証明可能な自然数
例: ふぃっしゅ数ver6など、計算可能な手段で求められるもの
(2)存在を証明可能だが、直観主義論理のもとでは証明不能な自然数
例: ある程度大きな入力に対するビジービーバー関数やラヨ関数、
その他の計算不能関数の出力？
(2)の数は、さっきの※みたいな、任意のn∈{0,1,2,...}についてnより大きい
としても無矛盾、といったやや奇妙な性質をもつようになると思われる。
続く (3)存在を仮定するとω矛盾であることが導ける、したがって自然数論からは
おそらく存在が証明不能であるが、無矛盾性は強くしない自然数
おそらく、としたのは自然数論が矛盾していれば何でも証明可能であるため。
例: 「自然数論の矛盾の導出を試みて、導出したら停止する計算機械」
が停止するまでにかかるステップ数
自然数論 + (自然数論は矛盾)という公理を採用すれば停止することを証明可能で、
自然数論が無矛盾ならば(自然数論は無矛盾)は導出できないため、
自然数論が無矛盾ならば、自然数論 + (自然数論は矛盾)もまた無矛盾
よって無矛盾性は強くなっていない。
(4)存在を仮定すると、ω矛盾になるうえ、無矛盾性も強くなるが、
矛盾はしないような自然数
集合論では、大きすぎて存在を仮定すると無矛盾性が強くなるような
濃度のことを巨大基数と呼ぶのだった。いわば、(4)は自然数論版の
巨大基数である。ただしこれについての研究はほとんど無いから、
具体例を挙げるのは難しい。
(3),(4)に属する自然数は超準数で、したがって(1),(2)に属するどの自然数よりも大きい。
(1),(2)は存在を証明できる自然数で、(3),(4)は存在しないとは証明できない自然数である。
(4)に属する自然数はおそらく(3)に属する自然数よりも大きい。 ちなみに>>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)のどれにも属さない、
存在を仮定すると矛盾が導ける数、ということになる。 あっ、そうだ。
>>39
さすがに0の逆数っていうのは先述の通り矛盾するからないけど、
どんな実数よりも大きい超実数という数の存在を仮定して色々する
超準解析っていうのがあるよ。 >>47
通常の算術が成り立たなくなることは理解しました。ありがとうございます。
スレチってこともあるのであまり深くは掘り下げないことにします。
そういえばu=u+1って式はuが可算集合濃度だと成立する式ですね。この場合は辺々uを引く操作に意味がないわけですが。 >>45
ビジービーバー関数が存在することに疑問の余地がある？ >>45
ビジービーバー関数の何が証明不可能だと言ってる？
Σ(9^9^9)が明確に定義されていて存在することは明らかだよね？ 少なくとも、存在することが証明できる数でないと探索にならないのでは？
到達不可能基数のような、巨大基数を仮定すると定義できる巨大自然数
みたいなのがあるの？
関数であればそういう物もあるような気がするけど、
単なる１個の自然数にそういうのがある？
自然数に計算可能も計算不可能も無いよね？ スレを計算可能レベルと不可能レベルに別けるのは構わないっちゃあ構わないけど、
不可能レベルだけでそんなに話題があるだろうか？ と思って前スレみてみたらそこそこあるな >>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), … のいずれも反証可能ということではないので スレの統一ルールはないので、計算可能でも不可能でも、自分が好きな話題を出せばいい 数年に1スレ消費するような閑散としたスレッドで、前スレは久々に1年以内に消費した
程度なんだから、話題なんてごった煮でよくて、巨大数に関することは基本的になんでもあり 公理 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)の具体例を超えることも十分に考えられるな。 順序数や基数は整列集合だから
○○を満たす最小
みたいなのがあるわけで
整数だと
nが○○を満たせばn-1も満たすから
そういう形で大きな数を定義するのは無理では？ >>57
公理系によってBBの値は変わらんよ
公理系で証明可能だろうが不可能だろうが
BBの値に影響無い
単に選んだ公理系に証明の能力が無いだけ 選んだ公理でマシンの動きが変わるなんて事はあり得ない BB(M)の大きさを語るのに
その大きさをまともに扱えない公理系を使うのが間違い
幼稚園児がBB(4)=14の矛盾を導けないからといって
BB(4)=14と教えれば幼稚園児にとってはBB(4)=14である
と言ってるようなもの 計算可能な関数も
公理によって値を返すかどうか証明不可能なものがあったと思うけど 公理系の強さが順序数で表されるというのは興味深い。
深く勉強してみたいものだ。 二階部分を量化して任意の部分集合は最小値をもつと言えば自然数論の超準モデルと区別できるようになる >>62
少なくともZFCにおいては、BB(4) = 13 が証明されているから、
ZFCのもとで 4 は※をみたすほど大きな数ではない。
無数にある無矛盾な公理系のうちどれを採用すべきかは数学の範囲内
じゃ答えられないし、ある公理がもつ無数のモデルのうちのどのモデル
を採用すべきかも数学の範囲内じゃ答えられない。
しかも、ビジービーバー関数の出力をすべて決定できる無矛盾な公理は必ず
帰納的公理化不能になるから、そんな公理の採用を強制されても神様にしか
扱いきれない。
数学の範囲内で答えられないなら哲学の出番になるけど、俺は哲学的議論
なんてしたくない。決着がつくことはほとんどありえないからだ。
俺はそんな哲学的議論をするより、あくまで数学の範囲内で、
そして人間が扱える公理の範囲内で、考察対象がもつ性質について
述べる方がずっと面白いと思う。 BB(M)が扱える公理系ならどの公理系を選んでも値は同じ
どの公理系を選ぶかなんて考える必要は無い
その辺はBB(4)となんら変わらない 大きい数を競うのに、
実際に値を求める必要は全くなくて、
大小を比較する手段があれば十分 どんな公理を選んでも「決定できない」ものを「定義された」とみなすかどうかの話。
定義できたとみなしたときに、それを「チューリングジャンプ」とか「神託機械によって
計算された」と表現するので、計算可能性理論の領域に入ってくる。 >>25
>「十分大きな自然数Mについて、0 < BB(M), 1 < BB(M), 2 < BB(M), ...が証明可能」
>は証明できてないけど、もっと弱い主張である※ならば簡単に証明できる。
これがおかしい。ビジービーバー関数はFOSTで記述可能、
よって1階述語論理の完全性により、任意の自然数ｎにつきあるaがただひとつ存在し、BB(n)=aを
証明可能 超準モデルは>>66で否定できる。よってビジービーバー関数の値が超準的自然数にならないように
定義することもできる、というかそういう定義だよな？ 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 >>66 もっと詳しく。urlでもいい。
>>69 公理とモデルごっちゃにしてない？
>>73 >>25は別に∃a(BB(n)=a)が証明不能とは言ってない。
BB(n)=0,BB(n)=1,...の内のいずれも証明不能なのは>>57の通り>>25の※から導けるけど。 >>76
∃a(BB(n)=a)ではなくBB(n)=aが証明可能、つまりBB(n)=0,BB(n)=1,...の内のいずかが証明可能
であり※は誤り、という主張です >>26はMがどこまでも大きくなればBB(M)もどこまでも大きくなる、ということを証明しているんじゃ？ あと
>N個を超える1を出力した時点でそのチューリングマシンは停止しないと判定できる。
N個を超える1を出力した後にその1を消して停止することも考えられるのではないでしょうか？ >Mがどこまでも大きくなればBB(M)もどこまでも大きくなる、ということを証明しているんじゃ？
これはこちらの勘違いでした、スマン >>79
BB(n) = 0, BB(n) = 1, ...のいずれかが(帰納的公理化可能な公理から)証明可能なら、
>>26と似たような計算機械、すなわち
BB(n) = 0の証明を試みる子プロセス、BB(n) = 1の証明を試みる子プロセス、...
を次々生成する親プロセスを作り、子プロセスが一個でも証明完了すれば
得られたBB(n)を出力して全プロセスを終了、とすれば子プロセスの1つは証明完了
することは確実なので、BB(n)を計算できる機械が作れ、BB(n)の計算不能性と矛盾 >>80
優勝者よりも多くの1を書きながらそれを消して停止するマシンの存在は
確かにありそうで、その点で>>26には問題があるけど、
「N個を超える」のところは「N*2個」とか「N^2個」、はたまた「2^N個」
「Ackをアッカーマン関数としてAck(N, N)個」と置き換えても停止性問題を
解ける機械が作れるという結論に変わりなく、わざわざAck(N, N)個以上書いた1を
N個未満になるまで消してから停止するマシンがあるのに優勝マシンにはたったの
N個しかテープに1が無い、っていうのは(証明はしてないが)考えにくい。
だから結論は疑っていない。 あ、テープにある1の総数は増やさないけど停止しないものもあるじゃん。
例えば0を読み取ったら状態も文字も変えずただ右にシフトするだけだったら、
空のテープをずっと右に行くだけで停止しないのに1の数は0個のままだから
停止しないと判定されることもない。
>>26 はまずいな... ビジービーバー関数じゃなくて最大ステップ数関数に
譲歩したほうがより安全か。 >>26については>>35でおしまいじゃないの？
どこまで計算しても「計算がいずれは終了するのか永遠に終了しないのかを判定する
一般的アルゴリズムは存在しない」ことが停止性問題。最大値を確実に見積もれたら、
その最大値まで計算すれば判定ができてしまうので停止性問題が解決してしまう。
つまり、>>26の仮定がおかしいということ。 まあ背理法で示す訳だから矛盾を導くためのおかしい仮定をするのは当然だが、
>>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))から、結局は※と同じことを導出できるな。 >>66の任意の部分集合が最小値をもつのと、
超準モデルを否定できるのとのつながりが分からない。 >>26
子プロセスの「矛盾を導出する」のはチューリングマシンと同じ能力の計算機械で出来るの？ 停止性問題は任意のチューリングマシンの停止性を判定するアルゴリズムは存在しないというだけで
特定のチューリングマシンの停止性を判定できても矛盾はない・・・よな
超準モデルは必ず無限下降列をもってたと思う それぞれのMにつき、状態数Mのチューリングマシンの停止性を判定するチューリングマシンが
それぞれに存在するだけなら停止性問題に触れない >>86
なるほど。「詳細は省くが」のところが、けっこうすごいことやったのでは？ >>88
一階述語論理の健全性と完全性より証明可能⇔恒真
帰納的公理化可能な公理から証明可能な式は枚挙可能
よって証明可能な式を枚挙していれば必ず恒真な式は証明される
>>89
ZFCの無限公理が存在を保証する集合をNとして、ZFCが無矛盾なら、
ZFCに定数記号 v を加え、ZFCに v ∈ N という式を加えても無矛盾
{} ∈ v, {{}} ∈ v, {{}, {{}}} ∈ v , ...の式を有限個加えても無矛盾
よってコンパクト性定理より、
ZFC + (v ∈ N) + ({} ∈ v) + ({{}} ∈ v) + ({{}, {{}}} ∈ v) + ...もまた無矛盾
これをZFC*とすれば、ZFC*のモデルはZFCのモデルでもあるが、超準モデルである。
ZFC*は正則性公理を含むので、ZFC*のモデルの中の集合は∈の無限降下列を持たない。
よって無限降下列が有無を根拠に超準モデルを排除できる訳ではない。
この事実をあえて解釈するなら、超準モデルの中では超準数は有限にしか見えない、
だから自分が超準モデルの中にいるのか標準モデルの中にいるのか分からない、
といったところか。 >>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 個の状態数があれば足りる。
省いた理由が分かってくれるとうれしいな。 さて、書きたいことは書いたし、もうスレからおいとまするか。
あ、巨大数探索スレだから一つ巨大数を提示してからにしよう。
X = "「自然数論から矛盾の導出を試みて導出したら停止する計算機械」が
停止するまでにかかるステップ数"
自然数論が無矛盾ならXの存在を証明できないし、ゲーデルの不完全性定理より
Xの存在の否定も証明できない。
そして、任意の n ∈ {0, 1, 2, ...}について、 n < X が証明可能、すなわち
0 < X, 1 < X, 2 < X, ... がいずれも証明可能である。
これを巨大数と認めるかどうかは哲学の問題だから俺は言及しない。 >>94
定義が曖昧過ぎませんかねえ
哲学とか言う前に >>91
別にそこはどうでも良いよ
21倍も状態を持てば押さえ込むのは簡単だし
そんなことをしなくとも
シフト関数と大差ないわけだし 自然数論が無矛盾なら停止しない
矛盾していれば停止する
無矛盾を前提にすると停止しないので値は存在しない 任意の超準数uにつき、0でない限りひとつ前の数が存在するのでu-1が存在する。
u-1も超準数である。
以下u-2,u-3,・・・とつづき無限下降列となる
コンパクト性と相いれないのは変だな、自分がどっかで何かを勘違いなり間違いなりしてるんだろう 任意のチューリングマシンは有限時間で停止するかしないかのどちらか
有限個のチューリングマシンの中には有限時間で停止するチューリングマシンが有限個存在する。
有限時間で停止するチューリングマシンの出力する情報の容量なり停止するまでのステップ数なりは有限
有限個の値の中には最大値が存在する。
ビジービーバー関数がこれ以上公理を仮定する必要が無くwell-definedであり、
普通の自然数を返すこと自体は明らかじゃないか？ 根本的にビジービーバー関数が定義で標準モデルを指定してないと考えてること自体が間違いかもしらん。 無限下降列をもたないというのは2階の性質になるからコンパクト性と相容れなくていいってことか？ >>26は最大シフト関数に置き換えて考えるとして、Mの値が限りなく大きくなれば子プロセス
のプログラムも限りなく複雑になる、ということはない、という証明が必要では ビジービーバー関数
を越えるには
チューリングマシンに神託を加えれば良い
どんどん加えていくことでチューリング次数による
順序構造が出来る
計算可能関数の時と同じように
大きな順序数を作ることで大きな関数が出来る チューリング次数が自然数の時はイメージ湧くけど
チューリング次数がωとかε_0とかも考えられるの？ 全ての有限次チューリングマシンの停止性判定が出来るのがω次チューリング機械とか？ ふぃっしゅ氏はビジービーバー関数のチューリング次数を数え上げてたけど、それとω次TMとはちょっと違う気もする。チャーチクリーネ順序数上では同じ表記になりそう。
ラヨ数とふぃっしゅ数v4の間の構造の関係もも知りたい。
ふぃっしゅ数v4から何が起こるとラヨに到達するのか。
ラヨ数をチャーチクリーネ順序数表記するとどうなるのか https://ja.m.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E6%AC%A1%E6%95%B0
自然数の集合に対してチューリング次数が決まる
ビジービーバー関数の値となる自然数だけ集めた自然数の集合はチューリング次数0^(1)
この集合を利用できるチューリングマシンのビジービーバー関数の値だけ集めた自然数の集合はチューリンク次数0^(2)
集合0^(n)の情報を全て集めたのが0^(ω)
情報の集め方は、f : N^2 --> N の単射から作れる
当然0^(チャーチクリーネ)等も作れる 可算順序数は基本列が存在するので
全ての可算順序数に対応するチューリング次数である自然数の集合が存在する
チューリング次数は全順序ではなくて、0^(0)と0^(1)の中間のような中途半端な物も存在するが
巨大数探索の為には順序数に対応するチューリング次数だけ考えれば良いような気がする 0^(1)を使えばチャーチクリーネ順序数の基本列が作れるし、
より次数が大きければ、より大きな可算順序数が作れる
大きな順序数から次数の大きな集合を作り
次数の大きな集合から大きな順序数を作る
これを繰り返すことで到達する順序数は非常に大きいが
名前はついているんだろうか recursively inaccessible ordinals
recursively Mahlo ordinals
nonprojectible ordinals
stable ordinals
...
いろいろな巨大可算順序数が書いてありますね 大きな可算順序数αが定義出来たら
巨大数を定義するために
チューリング次数0^(α)の集合たちの中から１個を選ぶ必要があるが、
簡単に１個を選択(定義)することが可能だろうか？
チューリング次数0^(α)の集合たちは可算個存在する
適当に順序を付けて最小が決まれば良いのだが、
最小値があるように順序を決めるのは難しそう
決まらないのであれば、αの基本列を構成して行かねばならない
これは定義が非常に複雑になるので、避けられるなら避けたい ■ このスレッドは過去ログ倉庫に格納されています
