巨大数探索スレッド13
■ このスレッドは過去ログ倉庫に格納されています
大きい数を競うのに、
実際に値を求める必要は全くなくて、
大小を比較する手段があれば十分 どんな公理を選んでも「決定できない」ものを「定義された」とみなすかどうかの話。
定義できたとみなしたときに、それを「チューリングジャンプ」とか「神託機械によって
計算された」と表現するので、計算可能性理論の領域に入ってくる。 >>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^(α)の集合たちは可算個存在する
適当に順序を付けて最小が決まれば良いのだが、
最小値があるように順序を決めるのは難しそう
決まらないのであれば、αの基本列を構成して行かねばならない
これは定義が非常に複雑になるので、避けられるなら避けたい 計算不能領域の話題が盛り上がるとは思ってなかったわ。
正直スマンかった。 wikipediaからコピペ
恒真論理式全体の集合は（言語にアリティ 2 以上の述語が一つでも含まれていると）決定可能でない。つまり、
任意に論理式が与えられたとき、それが恒真であるか否かを判定するアルゴリズムは存在しない（「チューリング
マシンの停止問題」を参照）。この結果はアロンゾ・チャーチとアラン・チューリングがそれぞれ独立に導き出した。
正確には、恒真論理式のゲーデル数全体の集合は帰納的でないということである。
それでも、与えられた論理式が恒真であるとき、かつそのときにのみ 1 (yes) を出力して停止するアルゴリズムは
存在する。ただし、恒真でない論理式を入力した場合はこのアルゴリズムは停止しないかもしれない。これを、
恒真論理式全体の集合は準決定可能であるという。これは正確に述べれば、恒真論理式のゲーデル数全体の
集合が帰納的可算であるということである。
ビジービーバー関数の値は決定しているけど計算不可能であるというのはこれで説明できるんじゃないだろうか 上のは恒真式の集合が決定可能である、すなわちアルゴリズムが存在しなければ証明不可能
としていたのが誤りだったということだろうか なんか理解できないのでとりあえずビジービーバー関数の強化版を置いときますね。
Σ^[0](n)=Σ(n)
Σ^[a+1](n)=Σ(Σ^[a](n))
Σ^[0,a](n)=Σ^[a](n)
Σ^[b+1,0](n)=Σ^[b,n](n)
Σ^[b+1,a+1](n)=Σ^[b,Σ^[b+1,a](n)](Σ^[b+1,a](n)) >>118
そのような「”Σ” を使ったあらゆるチューリング計算」の中で最強を指示したのがふぃっしゅ数バージョン４の第１段階目であるs’(1)f(x)。この時点で>>118よりも大きい。
第２段階は「”s’(1)f” を使ったあらゆるチューリング計算」の最強を指示するs’(1)^2f。第３段階、第４段階…と行き、段階を対角化する事で有限段階では辿り着けない第ω段階目のs’(2)fに達する。
「s‘(2)fを使った」が第ω+1段階目のs’(1)s’(2)f。第ω+2のs’(1)^2s’(2)f、第ω+3のs’(1)^3s’(2)f、を対角化した第ω×2のs(2)^2f、それもさらに対角化した第ω^2がs’(3)f。
それをさらに対角化したのが第ω^ωのs’(x)f、そしてさらにそれを63回ss’(x)変換した第(ω^ω)×63の先がふぃっしゅ数バージョン４。 と書いてて思ったこと。こんな風にふぃっしゅ数バージョン４はビジービーバー関数とふぃっしゅ数バージョン３を組み合わせて作られてる。
でもせっかくビジービーバー関数という「あらゆる計算の中で最強の手順を探してくれる」機構があるのに、再帰部分はふぃっしゅ数バージョン３っていう「手作り」機構なんだよね。ここもビジービーバーライズできないものか。 >>109 で recursively inaccessible ordinal 相当の関数が作れる >>119
こういうイメージ？
Σ(x)は、ビジービーバー関数
「f→g(x)」=「『fを使ったあらゆるチューリング計算』の中で最強を指示したものをg(x)とする。」
Σ→Σ^[0](x)
Σ^[a]→Σ^[a+1](x)
Σ^[ω]→Σ^[0,0](x)
Σ^[b,a]→Σ^[b,a+1](x)
Σ^[b,ω]→Σ^[b+1,0](x)
Σ^[ω,ω]→Σ^[0,0,0](x)
Σ^[c,b,a]→Σ^[c,b,a+1](x)
Σ^[c,b,ω]→Σ^[c,b+1,0](x)
Σ^[c,ω,ω]→Σ^[c+1,0,0](x)
Σ^[ω,ω,ω]→Σ^[0,0,0,0](x)
...........
Σ^[ω,...n個...,ω]→Σ^[0,...n+1個...,0](x)
Σ^[ω,...ω個...,ω]→Λ(x)
Λ(Λ(Λ(...63回...Λ(x)...))) ビジービーバー関数みたいな強力な関数に対して
ゴミみたいな量を増やして喜んでるのって
どういう心理？
>>118とかふぃっしゅV4とか 巨大数を生成するシステムが最終的に何を出力するか、計算可能か計算不可能かというのは表層上の
問題な気がする。オラクル無しの1階述語論理の対角化でラヨ関数（本当はFOSTだけど）になる一方で、
1階述語論理よりもはるかに強い高階述語論理を計算可能レベルで実装したCoCの対角化したloader.c
というものもある。
Little Biggedonとか計算可能レベルに応用できそうだがな、どうだろう
真理述語を限定的な停止性の判定に置き換える感じで >>128
どういうとんでもなさを想定してる？
単にa_n=a^nとしてもaを1か-1に近づければ望みの遅さで収束・発散する数列が作れるけどそれじゃ満足しないんだよね？ >>131
そうですね
グッドスタイン数列を越えたいです >>129
V7も同じ
強力な武器に対して+1しただけ
そもそも、これらは細部が書いてない為定義として完成してない >>128
増加度の大きな関数の逆関数もどきを使えば作れる
例えば
f(n) を Σ(m)≧nとなる最小のmとして
a[n] = 1 / f(n) みたいな コルモゴロフ複雑度Kを用いて
a[n] = 1 / K(n)
とすると>>134とほぼ同じ 増加度の大きな関数の値が分母にくるようにするわけですか？
すると数列は0に収束する事になるわけですが、分母がすぐ大きくなるから収束速度がとんでもなく早くなる気がします >>133「これら」ってことはラヨ関数も完成してないってこと？ は？
>>134のfも>>135のKも
非常に増加度が遅く、無限大に発散する関数
だから、その逆数であるa[n]は非常にゆっくり0に収束する 今のところ計算不可能レベルで何が完成していると見なされているのか聞きたいです >>138
そうなんですね！
ごめんなさいよく知らずに
精進します >>140
一番簡単なのだとビジービーバー関数
ふぃっしゅ数V4は機械の定義が一切無い
こんなんで「定義」として本まで出しちゃうとか
なかなか想像を絶する V4はオラクルの具体的な実装が定義されてないということでわかる。
でもV7はちゃんとwell definedになってないか？
あとΞ関数はごみではない？ 定義自体にゲーデル数化は必要なくない？ ほかの言語で定義する際に必要になるだけで >>144
具体的な実装が書いてないのはむしろ「ビジービーバー関数」の方に文句言わなきゃ。それがありならこれもありでしょ的カウンターでしょF4は >>146
そうなのか
良く読んで無かった
>>147
ビジービーバー関数はちゃんと定義されてる
機械の動作の細部まで いずれにしろ
V4やV7は強力な武器に対して+1しただけ
全く価値がない
ゴミ ふぃっしゅ数V7はラヨ階層を定義したのならそれを言語の中にぶっこんで対角化した強さを
とればよかったんじゃって思う。適当な見積もりだけどBIG FOOTくらいになるんじゃなかろうか >>148
いや、定義されてない。
ビジービーバー関数の中で具体的な実装が定義されているのは候補となるチューリングマシンの動作までであって、
どのチューリングマシンがビジービーバーであって最大の出力をするのかを選ぶというビジービーバーの本質部分の方法についてはv4のオラクル同様具体的な実装が定義されていない。 >>153
「どのチューリングマシンがビジービーバーであって最大の出力をするのかを選ぶ」
ための手順がわかってしまったら、それは計算可能だということになってしまう。
それができないというのが停止性問題。 >>153
君の中では円周率も定義されてないって言うのかな？
値を正確に計算する方法が無いわけだけど >>155
それこそv4でオラクルの具体的な実装の定義がなされてないからダメって言ってる>>144に言ってやれよ。
俺は「そこはビジービーバー関数も同じだろ、だからv4だけが責められるのはおかしい」って言ってるだけ。 計算不可能関数なんだからビジービーバー関数もオラクルをひとつ持っているんだよ
F4がオラクルをはじめて使い出したんじゃない V4はマシンの動きが定義されてない
普通のチューリングマシンは動きが定義されている >>153
「定義されていない」の主張ではなく「計算できない」ことを懸命に主張してるようにしか見えないんだけど ビジービーバー関数は定義されている。
ふぃっしゅ数V4はオラクルがどう引数を受け取ってどう関数fの値を返すのかって部分が曖昧。
たとえばそのオラクル状態に入ると、その時点でテープに入力されている1の数をnとし、
その時点のヘッダの位置から右に向かって1をf(n)個上書きするとか1マスおきに上書きするとか
f(n-1)+1個上書きしてヘッダの位置を1番左の1まで移動させるとか考えられる。 曖昧とかそういうレベルじゃない
一切定義が書いてない
「関数fを神託として持つチューリングの神託機械を考え」
これだけ チューリング完全を保ったままfを実行出来れば動作は何でも良い
決めるべきは
fを実行する条件
fのパラメータの受け取りかた
fの返し方
もしかしたら、
fの取りうる値の位置だけ値が1
それ以外が0
をテープの初期状態として動作するだけでも良いのかもしれない オラクルの渡し方は>>163のテープの初期状態だけで良さそうだね
これでチューリング次数を1個上げられる
チューリング次数が0でなければ
fの値が偶数になるもの、奇数になるもの
いずれかは無限に存在する
fがオラクルチューリングマシンのビジービーバー関数であれば
無限に存在する方(のうちの一方)の情報だけでもチューリング次数は変わらない
無限に存在する方(のうちの一方)を保存しておいて
他方を制御に使えば良い fを実行する条件は普通の状態と同じように外部変数に委託していいだろう。
A状態で1を読み取ったらヘッダを右に移動させてオラクル状態に入るとか
しかしオラクルを重ねるとかしない限りV４の本質的な強さは決まっているものかと。 Ξ関数の強さはω^CK__1なのか、それとももっと強いのか？
前者ならふぃっしゅ数V4より弱い オラクル状態って何だ？
いちいちマシンの状態を分けるのか？
>>164が一番シンプルだと思うが
決めるべきことが一番少ない
----
自然数全体の集合の部分集合Sをオラクルとしてマシンに与える
通常のチューリングマシンはテープが全て0の状態で動作を開始するが、
オラクルマシンは集合に含まれる自然数に対応する位置を1にして動作を開始する
開始時のヘッドの位置は最小の自然数に対応する所とする
このマシンにたいするビジービーバー関数を
Σ[S](n) とする
これでオラクル付きビジービーバー関数の定義は終わり
関数fに対しては
Σ[f](n) = Σ[f(自然数全体)](n)
と定義すれば良い おっと
停止時の1の数だと無限になってしまう
1の増分にしないと
あまり美しい定義じゃなくなっちゃうので
最大シフト関数でいいか ■ このスレッドは過去ログ倉庫に格納されています
