巨大数探索スレッド13
■ このスレッドは過去ログ倉庫に格納されています
無限下降列をもたないというのは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の増分にしないと
あまり美しい定義じゃなくなっちゃうので
最大シフト関数でいいか まあそんな+1を考えてもしょうがなくて
素直にビジービーバー関数をも定義出来る言語n文字で定義可能な最大の整数
で良いわけで
そのひとつがラヨ関数
言語の自由度をどんどん上げていって
矛盾スレスレにすれば自然と大きな数が定義出来る チューリングの神託機械自体はすでに定義されているものなので、
どうせ計算しないんだから複雑度がわかればよくて実装はなんでもよくて、
wikipediaのoracle machineにはvan Melkebeekの実装が書かれている >>169 1の増分だと|ω+n|=|ω|で濃度は変わらない、が、言わんとしていることは分かる。
>素直にビジービーバー関数をも定義出来る言語n文字で定義可能な最大の整数
>言語の自由度をどんどん上げていって
>矛盾スレスレにすれば自然と大きな数が定義出来る
オラクルの追加も言語の自由度を上げていくことになるし、このやりかた自体を否定しちゃうと
BIG FOOT やLittle Bigeddonもごみ認定されかねない。されてるのかもしれないけど
>>168の定義でω^CK__2に達しているのかどうかがちょっと気になる。 複雑度は変わらないから実装は何でもいいって言っちゃうと、急増加関数+順序数で定義しても
いいってことになっちゃうと思う。それはそれでありだけど数と言うよりは指標って感じ。
オラクル状態ってのは>>161の動作をした後ヘッダの位置と次の状態で定義される。オラクル状態に
入った瞬間のテープの読み取り方にいくらかパターンを与えてもいいだろう。
>>171で調べてみたけど実装の仕方いくらか考えられているのね >>171
どう定義してもいいけど、定義されてないと定義にならんでしょ >>172
変化するのは有限個だから増分と言えば意味はわかるでしょ
>>168の定義でいいのは>>164で説明したつもり
不足なら説明を追加するけど >>86
どうやっても21倍もかからない
とりあえず8倍では出来た >>164
テープのプラス側はオラクル情報として残しておいて
テープのマイナス側だけ制御に使えば良いのか
こっちの方がチューリング次数的には明確
オラクルに制限を付ける必要が無く
自然数の集合であれば何でも良い てことで、
オラクルはテープの初期状態で渡せば良い
これが一番定義がシンプル >>177
テープのマイナス側の適当な所にプラス側の情報をコピーしながら動作する
適当な所とは例えばオラクル情報のコピーはマイナスの偶数位置
制御情報はマイナスの奇数位置とか
オラクル情報が必要な時に、
必要に応じてコピーして使う
これで、チューリング完全を保ったままfを好きな時にコールする仕組みが出来た せめて歴史的経緯も考慮しておかないと最新最強以外は全部ごみになると思うわ ビジービーバー関数やオラクルは基本単語という感じ
当然知っておくべき
順序数やハーディーも基本単語 あんまり結果ばかり追求して過程を省みないと「すごいこと知ってるんだね、でも中身スッカスカだね」
てなるわ 計算可能レベルの階層と理論の証明論的強さの研究くらい認めてもいいだろう。 >>186
巨体数に結びつかない屁理屈は続けてほしくない 計算不可能関数使って巨大数の結果を出せても計算可能性のすべてを理解できたということにはならないし、
それって計算複雑性の研究を屁理屈言ってるようなもんだ 結局どんなに有限の巨大数を探索しても「それってωよりも小さいじゃん、下らない」って言ってるのと
同じじゃ 計算可能性のすべてを理解したい人
有限の巨大数の探索は下らないと思う人
は他のスレに 計算可能関数を通じて個人的にも巨大数の理解に深めたい人はスレに歓迎したいと思う。 将来的に、ある強力な言語で記述できてしまうということでビージービーバー関数はおろかラヨ関数、
リトルビッゲドンまでゴミ認定されてしまいそうなのが嫌だったんだ、そういう人間も出てくるんだろうけど 圧倒的に大きい数が出てくれば、
それまで大きかった数がゴミになるのはしょうがないかと
大きさ的にゴミの中でも、
アッカーマン関数、ビジービーバー関数のように、
巨大数の基礎として知っておくべきものと
単なる価値の無いゴミとに別れる
グラハム数の階乗、ビジービーバー関数のアッカーマン関数的拡張、
オラクルビジービーバー関数のふぃっしゅ数V3的拡張など、
強力なアイデアに対して+1しただけの数は
単なるゴミ ■ このスレッドは過去ログ倉庫に格納されています
