巨大数探索スレッド13
■ このスレッドは過去ログ倉庫に格納されています
>>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しただけの数は
単なるゴミ >>203
じゃあ>>118みたいなのも含めて全部大事にしてください とりあえずビジービーバーとラヨの間はマイルストーンが何個か飛んでる気はする
外伝でいいからしっくりくる何かで埋めたい 何かがつまらないと思う人は、そう思っていれば構わない。
自分が面白いネタをいくらでも投稿してくれ。
ただつまらないというだけの投稿は一番つまらない。 >>208
両方とも、
ある言語n文字で定義可能な最大の数
ということで非常に似てると思う 「大きな実数を探索するスレッドです」
感覚麻痺しちゃってるかもしれないけどグラハム数だってものすごく大きな実数だからな、一般的な感覚からすれば 古くなったものをそう簡単にゴミゴミいうのも失礼だと思うし、自分の価値観を押し付けて他人の価値観を
見下すのもどうかと ふぃっしゅ数V4がサラダ的と言うのは正直、同意できる チェーンはコンウェイのチェーン表記かな
タワー表記
日本語ウィキぺディアに書いてあるけど
英語のウィキの誤訳か？ ■ このスレッドは過去ログ倉庫に格納されています
