巨大数探索スレッド7
■ このスレッドは過去ログ倉庫に格納されています
0001１３２人目の素数さん
2006/11/19(日) 23:44:01http://www.geocities.co.jp/Technopolis/9946/
前スレ、過去スレ、避難所はこのページからどうぞ。
「前の数＋1」
「1/x x→0」
「∞」
「９を延々と書き続けるプログラム」
「本日からこのスレでは、いっさいの数学的ではない話を禁止する。
私以外で検証する能力を持っている人間はいないようなので、
数学的に明確に証明できた場合以外は反論しないように。
特に今日のような低俗な煽りには徹底して放置で対応すること。」
という類の投稿は放置推奨。
0314１３２人目の素数さん
2007/08/24(金) 23:19:54> ack(4,n)=2^(2^n+3)-3
> ack(5,n)=2^(2^(2^n+3))-3
これじゃ原始帰納だよ
0315１３２人目の素数さん
2007/08/25(土) 01:48:40> ^以降では、交換法則が不成立性なのはすぐわかるんだが、結合法則はどうやって示すんだろ
(3^3)^3 ≠ 3^(3^3)
> ackについては、もう少し書くと
どこをたてよみ？
> hardy functionに関しては、n<ωの時はこうなるよな？
「hardy function に関しては」と書いているのに hardy function が出てこない不思議。
>> そういう他に依存した定義をするズルとは違う。
> 違わないと思う。
自分が理解できないからってズルか。
あたまがわるいふりをした釣り？
0316１３２人目の素数さん
2007/08/25(土) 04:16:19ackとチェーン表記については、ack(m,n)=2→(n+3)→(m-2) - 3という関係式が成り立つようだ。
ただ、m=0を代入すると右辺の計算ができないからm>0とする。
（a→b→(-1) = a+b, a→b→0 = a*bとしておく）
どうやら、>>306では「階乗」という言葉を"！"以外の意味で使いたかったようだな。
hardy functionに対しては何を言いたいのか分からないので、
もう一度hardy functionのことを勉強してから書き直してほしい。
ビジービーバー関数みたいな定義をズルと感じるかどうかは、人によって違うかもしれない。
関数に対して具体的な計算手順を定めなければいけないと考えるなら、
ビジービーバーみたいな具体的な計算手順を与えない定義はズルだとも言える。
ただ、この場合は暗黙のうちに「計算可能」な関数のみを考えているということになる。
一方、関数というのはある引数に対してある値が定まりさえすればいいと考えるなら、
ビジービーバー関数もズルではないということになる。
いずれにしても、「今まで出た一番でかい関数+1」というのは状況によって異なる関数になってしまうから、
まともに定義しているとは言えず明らかなズルだと言える。
結局、客観的に見てズルかどうか判断するには、ルールや暗黙の了解が必要になる。
そういうものがあれば、それに反するものがズルだと客観的に判断できる。
現状では「計算可能」な関数に限るというルールも暗黙の了解もないから、
ビジービーバー関数がズルだと言っても単なる個人の意見でしかない。
ビジービーバー関数がズルだという主張も理解できなくはないけどな。
「今まで出た一番でかい関数+1」というのは他に依存した定義だから悪いというのなら、
他に依存しないように定義すればいい。他に依存しない定義をするためには、
あらゆる可能性をあらかじめ考えてその中で最大のものを選び出せばいい。
「あらゆる」といってしまうときりがないから、「ｎ文字以下のプログラム」とか制限をつければいい。
とやって行き着くところがビジービーバー関数だとも言えなくはないわけで。
0317１３２人目の素数さん
2007/08/25(土) 08:23:40> まともに定義しているとは言えず明らかなズルだと言える。
単に+1するのに14文字も費やして非常に効率が悪いのでだれも見向きもしないけど、
14文字である関数を非常に大きく出来るならそれはそれで意味があると思う。
S変換なんかは関数を大きくする変換だしね。
計算可能じゃない関数がズルだとかいっていたらそこで進歩は止まるよ。
虚数なんかは数じゃないといって否定するようなもの。
実際ビジービーバー関数よりずっと大きな関数も出てきてるし。
0318１３２人目の素数さん
2007/08/25(土) 10:28:26別に、計算可能じゃない関数がズルだと316で主張したいわけではない。
ビジービーバー関数に違和感を感じる人の気持ちも理解できなくはないというだけで。
個人的な考えとしては、計算可能な関数に限って大きいものを考えるのも、
計算不能な関数も含めて大きいものを考えるのも、どちらも意味あることだと思う。
実数の範囲のみで考えることも、複素数の範囲まで広げて考えることも、どちらも意味があるように。
0319１３２人目の素数さん
2007/08/25(土) 19:04:160320１３２人目の素数さん
2007/08/25(土) 21:56:26理解コストの高そうなのはスキップして前スレ一通り読んでみた。
俺の印象では計算不可能な巨大数だと、到達不能基数を除いてε数が強げ。
そんでωを表わすためのC言語の関数を考えてみた
big w(){return 1+w();} //bigは多倍長正数型(つか、値より停止性にしか意味ないような)
この関数の返す値(もちろん計算可能でない)をωとする
するとw()の多項式は、順序数ωの計算同様、右分配法則を満たさない
1+w()はw()に吸収されるからw()の値と同じ→1+ω=ωのアナロジー
n+w()はw()に吸収されるからw()の値と同じ→n+ω=ωのアナロジー
2*w()はw()に吸収されるからw()の値と同じ→2*ω=ωのアナロジー
n*w()はw()に吸収されるからw()の値と同じ→n*ω=ωのアナロジー
w()+1はw()で計算がとまる→ω+1≠1+ωのアナロジー。残りも同様
あと、ack3項版を作ってみた
1.ack(0,0,z)=z+1
2.ack(0,y,0)=ack(0,y-1,1)
3.ack(x,0,0)=ack(x-1,ack(x-1,1,0),0)
4.ack(x,0,z)=ack(x-1,z+1,0)
5.ack(0,y,z)=ack(0,y-1,ack(0,y,z-1))
6.ack(x,y,z)=ack(x-1,ack(x,y-1,z),ack(x-1,y,z))
☆ack(0,m,n)は2項のack(m,n)と一致する
停止性を満たしたまま1,2,5式を残せば☆を満たせる。
つまり、ackのn項化って色々やり方がある
多重帰納法の種類だけ、作れるんじゃなかろうか
0321１３２人目の素数さん
2007/08/26(日) 00:40:18> 俺の印象では計算不可能な巨大数だと、到達不能基数を除いてε数が強げ。
計算可能という意味をまず理解したほうがいい。
> big w(){return 1+w();} //bigは多倍長正数型(つか、値より停止性にしか意味ないような)
> この関数の返す値(もちろん計算可能でない)をωとする
無限ループとなり値は返らない。
> あと、ack3項版を作ってみた
複雑なわりに大して大きくなってない。
3変数ならもっとずっと大きく出来る。
0322１３２人目の素数さん
2007/08/28(火) 12:09:42ackやチェーン表記みたいな巨大関数の拡張案は過去に何度も出ているが、
その多くは元の関数にあった単純さを失ってる上にそれほど大きくないものになっている。
単純で巨大な計算可能関数としてはHardy関数があるし、
ただの拡張案で大きな関数を目指すことにはほとんど意味がないと思う。
あと、「ωはどんな自然数よりも大きい」とかの説明を聞くと、
順序数自体を巨大数として扱うのだと思ってしまう人がいるが、
順序数は単に巨大な自然数を作るための道具として使われてるだけのはず。
順序数から巨大関数を作るための手段の一つがHardy関数。
0323たろう
2007/08/28(火) 22:28:59これだけだと、単に大きな順序数を考えることと同じになってしまう。
Hardy関数、順序数やチューリングマシンの概念を使わずに
シンプルに、もしくは新しい方法で巨大な関数を作ることは十分意味があると思う。
Hardy関数と比較することで大きさの評価も比較的簡単になったし。
今のところHardy関数やチューリングマシンを使わない最大は、
ふぃっしゅ数バージョン５ （F[ε_0] 相当の関数） であろうか。
----
ちなみに、
>>320 のack は F[ω+ω](n) 程度の大きさ。
以下のように定義すれば、よりシンプルで F[ω^2](n) 程度まで大きくなる。
（こんな簡単な定義でコンウェイのチェーンでn個のnを結んだものと同程度になってしまう）
1.ack(0,0,z)=z+1
2.ack(x+1,0,z)=ack(x,z,z)
3.ack(x,y+1,0)=ack(x,y,1)
4.ack(x,y+1,z+1)=ack(x,y,ack(x,y+1,z))
※x, y, z は非負整数
多変数や多重リストへの拡張は >>281 の up2950.txt 参照。
0324１３２人目の素数さん
2007/08/28(火) 22:32:010325１３２人目の素数さん
2007/08/29(水) 09:39:080326１３２人目の素数さん
2007/09/03(月) 23:41:17A(n)では非負のnは1以下。パラメータの階層と、最上階層のパラメータの数はともに1。
A(0)=2 （初期値）
A(1)=A(0)^A(0)^A(0)=2^2=4
(=2↑↑2)
★２つ目の関数
この4が次のパラメータの階層と、最上階層のパラメータの数になる。すなわち、
A(n_1_1(n_1_2(n_1_3(n_1_4))),n_2_1(n_2_2(n_2_3(n_2_4))),n_3_1(n_3_2(n_3_3(n_3_4))),n_4_1(n_4_2(n_4_3(n_4_4))))
３つ目の関数に移行するためには、(5^(4*4)-1≒1.5^11)回の計算を経なければならない。
A(0(0(0(0))),0(0(0(0))),0(0(0(0))),0(0(0(0))))=A(1)=4
A(0(0(0(0))),0(0(0(0))),0(0(0(0))),0(0(0(1))))=4↑↑↑↑4=4→4→4
A(0(0(0(0))),0(0(0(0))),0(0(0(0))),0(0(0(2))))=(4→4→4)↑↑＜4→4→4個＞↑↑(4→4→4)
=(4→4→4)→(4→4→4)→(4→4→4)
A(0(0(0(0))),0(0(0(0))),0(0(0(0))),0(0(0(3))))=[(4→4→4)→(4→4→4)→(4→4→4)]→[(4→4→4)→(4→4→4)→(4→4→4)]→[(4→4→4)→(4→4→4)→(4→4→4)]=あ
A(0(0(0(0))),0(0(0(0))),0(0(0(0))),0(0(0(4))))=あ→あ→あ
A(0(0(0(0))),0(0(0(0))),0(0(0(0))),0(0(1(0))))=(あ→あ→あ)→(あ→あ→あ)→(あ→あ→あ)=い
A(0(0(0(0))),0(0(0(0))),0(0(0(0))),0(0(1(1))))=い→い→い
A(0(0(0(0))),0(0(0(0))),0(0(0(0))),0(0(1(2))))=(い→い→い)→(い→い→い)→(い→い→い)
★３つ目の関数
２つ目の関数の最後、
A(4(4(4(4))),4(4(4(4))),4(4(4(4))),4(4(4(4))))
はすでにグラハム数ですら無に等しいほどの巨大数となっている。仮にこれを「う」とする。
３つ目の関数は「う」の階層を持ち、最上階層の数が「う」のパラメータを持つことになる。
４つ目の関数に移行するには「(う+1)^(う*う)-1」回の計算を行わなければ成らない。
★64番目の関数
「ふぃっしゅ数」を軽く超えているものと予想される。
0327１３２人目の素数さん
2007/09/04(火) 02:32:05どのくらい大きいのかはよく分からないけど、なんだか昔の
スレッドに戻ったみたいでほのぼのした。
0328326
2007/09/04(火) 04:14:04○→○→○
だから、イマイチ増加率が大きくないことに気づく。
ただ、関数を１つ上げるために必要な項の増加率が膨大だから、どちらが大きくなるか。
語弊を招くことを承知で極論すれば、
「ある等差数列の1無量大数項目と、ある等比数列の百項目のどちらが大きいか」
と同じ話だ。
0329１３２人目の素数さん
2007/09/04(火) 10:01:57定義を誤解しているかもしれないが、思ったことを書いておく。
パラメータの数が多い割には、その多さが活かされていないと思う。
f(x)=x→x→xとすると、「う」というのは、f^{5^(4*4)-1}(4)と表される。
（f^n(x)は、xにfをn回適用した数とする）
n番目の関数でパラメータに最大値を代入したときの値をg(n)と表すと、
g(1)=4, g(n+1)=f^{(g(n)+1)^(g(n)*g(n))-1}(g(n))という漸化式でg(n)を表すことができる。
g(n)の大きさを見積もるためにHardy関数を用いると、
f(x)≒F[ω], g(n+1)≒f^{g(n)}(g(n))なので、g(n)≒F[ω+2](n)程度の大きさということになる。
過去ログによると、ふぃっしゅ関数ver.1はF[ω^2*63]程度の大きさということなので、
残念ながら326の関数ではふぃっしゅ数ver.1にも及ばない。
定義を解釈するときに、A(0(0(0(0))),0(0(0(0))),0(0(0(0))),4(4(4(4))))=☆として、
A(0(0(0(0))),0(0(0(0))),0(0(0(1))),0(0(0(0))))=☆→☆→☆のように計算するのだと解釈したが、
この解釈がもし間違っていたら指摘してほしい。
0330326
2007/09/04(火) 14:24:56はい、その通り。返す言葉もございません。
私も未明の書き込みの時点でふぃっしゅ数に遠く及ばないだろうと感じていた。
もともとこの式は、
・高校生でも理解できる関数（↑までは容易に理解できると思われるので）
・パラメータを爆発的に増やすことで「それなりに」大きな数を作ることを試みる
を満たそうと考えたのもので、これはその最も原始的なものという扱いです。
グラハム数やふぃっしゅ数とどちらが大きいかもまったく検証してなかった。ごめんなさい。
関数自体の増加率もパラメータの数もさらに増やすことは容易なので、
修正すればもう少し大きな数ができるかもしれない。
ふぃっしゅ数に勝てるかはわからんが、パラメータにも前項の式を代入できるようにすればあるいは…
0331331
2007/09/04(火) 18:44:150332１３２人目の素数さん
2007/09/04(火) 21:54:360333326
2007/09/05(水) 03:09:54つまり、ある項A_k+1はその前の項までAkを用いて、
A_k+1 = Ak^Ak^…(Ak↑↑Ak…(Ak↑↑Ak 回)…Ak↑↑Ak 回)…^Ak^Ak
A_k+1 = Ak^Ak^…(Ak↑↑↑Ak 回)…^Ak^Ak = Ak↑↑↑↑Ak = Ak→Ak→4
ある関数のパラメータは、その前の関数の最後の項の数Ｃだけ最上階層パラメータをもつ。
各最上階層パラメータはそれぞれＣだけ２次パラメータを持ち、さらにその２次パラメータはそれぞれＣだけ３次パラメータを持つ。
パラメータの階層はＣある。
すべてのパラメータmはm(i1,i2,i3,…,in)(1≦n≦C)と表記される。ここでi1,i2…は最上階層、次の階層…の値。
各パラメータには順序があり、i1が小さいもの、その中でi2が小さいもの、その中でi3が小さいもの、…から計算される。
たとえばC=3のとき、
A(あ(い(う,え,お),か(き,く,け),こ(さ,し,す)),せ(そ(た,ち,つ),て(と,な,に),ぬ(ね,の,は)),ひ(ふ(へ,ほ,ま),み(む,め,も),や(ゆ,よ,ら)))
とパラメータがおかれ、「ら」が最大値となったとき「よ」が1つ加算され、
「ら～せ」がすべてそれぞれ最大値となった時「す」が1つ加算され、となる。
また、あ→ら にかけて上位→下位のパラメータと定義する。
すべてのパラメータがそれぞれ最大値をとったとき、次の関数に移行する。
各パラメータは1からB(l)の値をとる。
ここで、あるパラメータの値が1つ下位のパラメータの最大値B(l-1)に達した時の、項の値をB(l)とする。
このとき、1つ上位のパラメータに移行するには、
B(l+1) = A_(k+B(l))
A_(k+B(l+1)) = A_(k+A_(k+B(l))) = A_(k+(Ak→Ak→4)→B(l)→2)
A_(k+B(l+1)) = (Ak→Ak→4)→((Ak→Ak→4)→B(l)→2)→2 (B(l)<Ak)
次の関数に移行するには…
やめた。326よりは確実に大きくなっているが、これだけややこしい説明してもグラハム数には及ばない。
高校生にも簡単に理解できて、かつグラハム数を超える数は作れないのか…
ちなみに高校生っていうのは、理屈の上ではタワー表記を使わずに説明できること（便宜上使ったが）
0334１３２人目の素数さん
2007/09/05(水) 05:20:32＞高校生にも簡単に理解できて、かつグラハム数を超える数
>>323の3変数アッカーマン関数で、ack(1,1,100)とするだけでグラハム数を超えると思う。
ack(1,0,x) = ack(x,x)=2→(x+3)→(x-2) - 3だから大雑把に見てack(1,0,x)≒3→3→xで、
ack(1,1,x)はack(1,0,x)をx回繰り返すのと大体同じくらいになるので、
3→3→xを4に64回適用したグラハム数よりack(1,1,100)の方が大きくなるはず。
左の方の引数を増やせば、もっと大きい数を作ることもできる。
そもそも、パラメータを増やすとごちゃごちゃしてくるのでかえって分かりにくくなってしまう。
あと、パラメータに最大値があるというのも、あまり大きくならない原因の一つだと思う。
それから、パラメータに階層構造があるのに、それが活かされていない。
たとえば、326の2つ目の関数では、括弧を取り除いて16個のパラメータを並べても同じ関数になる。
巨大数作りではよくあることだが、数を爆発的に大きくするための要点があって、
その要点をうまく抑えれば単純な定義でも非常に巨大な数が作れる。
逆に、その要点を外すとどんなに複雑な定義をしてもたいして大きくならない。
それがはっきり分かる一例としては、>>323の3変数アッカーマン関数がある。
たった3変数で、たった4つの定義式しかないのに、一番左の引数を大きくすれば
チェーン表記を伸ばすのと同程度の速さで増大していく。
0335326
2007/09/05(水) 06:09:38詳しい解説サンクス。
私も326を書き込む前に3変数アッカーマン関数を見て驚いた。
これは単純ながら強力だなあと感心した。
（じゃあ複雑化しただけで使い道のない関数作ってないでそれ使えよという突っ込みはなしで）
変数に関数自体を格納してしまうのが賢いとは分かっていながら、同じ手法使っても面白くないし。
読む気も失せる333だが、これは326を改良したものである。
どちらも結局、増加率には乗数しか使っていない。
パラメータにもなんら関数は格納していないし（順番に1ずつ増えていくだけ）、
ひどく原始的な手法で巨大数を作ろうという試みだ。
恐れ多くもこれでグラハム数を超えようとは呆れたものだ。
いまさらだが結局、乗数だけに頼っていては限界があるという愚例になったと思う。
（さらにまどろっこしい説明を加え続ければｘ→ｘ→ｘ→ｘを説明できないこともないが、無益なのでやめ）
0336ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/05(水) 21:24:49なるほど。ふぃっしゅ数バージョン５の意味付けをしていただき
ありがとうございます。
>>311
こうやって整然と比較できるのが、Hardy関数の威力ですね。
せっかくなので、これまでのふぃっしゅ数について
http://www.geocities.co.jp/Technopolis/9946/log/thread6.html
ここの531、544を参考にして大きさを評価すると、
ふぃっしゅ数バージョン1のSS変換n回：F[ω^2+1](n)
ふぃっしゅ数バージョン2のSS変換n回：F[ω^3](n)
ふぃっしゅ数バージョン3のs(n)：F[ω^ω](n)
といった感じになりましょうか。
ちなみに、
http://www.geocities.co.jp/Technopolis/9946/log/ln051.html
ここの115に出てくるSnakeは、どの程度の大きさになりますか？
>>323では、F[ω^2]程度の関数をシンプルに表記していますが、
F[ω^ω]程度、あるいはF[ε_0] 程度の関数を出来るだけシンプルに
表記するにはどうすればいいか？といった問題設定もできそうですね。
なにをもってシンプルとするかは主観ですが…。
0337たろう
2007/09/05(水) 22:39:13Snake の定義の３つ目の式を、
Snake([a<1>,･･･,a<n>],x)
=Snake([a<1>,･･･,a<n>-1],Snake([a<1>,･･･,a<n-1>,1],x))
と解釈し、
Snake([1],x) = x+1
とした場合は、
Snake([1がn個], n) ≒ F[ω^ω](n)
0338たろう
2007/09/05(水) 23:06:50>>260 でしょう。
>>281 でアップしたものをもう一度アップしておきます。
http://1rg.org/up/46579.txt.html
ついでに、定義自体に順序数を使わない大きな関数です。
概念的には順序数＋Hardy関数ですが、
順序数を知らなくても、頑張れば理解できるかも。
http://1rg.org/up/46580.txt.html
0339１３２人目の素数さん
2007/09/06(木) 01:36:03保存しておきます
http://symy.jp/m1mG
http://symy.jp/Lo51
0340ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/06(木) 23:12:12難しいですね…。
「概念的には順序数＋Hardy関数」とのことなので、
Hardy で F[ω^2], F[ω^ω], F[ε_0] に相当する
大きさの H[A] を作ると、Aの値はどうなりますか？
0341たろう
2007/09/07(金) 20:42:22H[((((0)))0)] ≒ F[ω^2](n)
H[(((0)0)0)] ≒ F[ω^ω](n)
H[((0)00)] ≒ F[ε_0](n)
H[(((0))00)] ≒ F[η_0](n)
H[((0)000)] ≒ F[Γ_0](n) = F[ψ(0)](n)
H[((0)(0)00)] ≒ F[Γ_Γ_...Γ_0](n) = F[ψ(Ω)](n)
H[(((0))000)] ≒ F[ψ(Ω^2)](n)
H[((0)0000)] ≒ F[ψ(Ω^3)](n)
H[((0)00000)] ≒ F[ψ(Ω^4)](n)
H[((0)00.....n個.....00)](n) ≒ F[ψ(Ω^ω)](n)
0342ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/08(土) 02:43:26まずは、>>338の定義をコピーします。
Ｎ:非負整数 とする (0, 1, 2, .....)
■集合Ｔ
○定義
0 ( ) の３つの文字からなる文字列の集合で、以下の２つの条件を満たす最小のもの
"0" はＴの元である
Ｔの元を１個以上有限個繋げて () でくくったものはＴの元である
演算子 + で文字列の連結を表す
"(0)" + "0" = "(0)0"
○意味
葉が0の多進木
0と多変数の関数funcで生成できる数 と対応する
"(000)" => (0,0,0) => func(0, 0, 0)
"((0)0(0)((0)0))" => ((0),0,(0),((0),0)) => func( func(0), 0, func(0), func( func(0), 0 ) )
0343ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/08(土) 02:44:25○定義
Seq は Ｔ×Ｎ から Ｔ への関数であり以下を満たす
s = "0" の時
Seq(s, i) は未定義
s = "(" + □ + a + ")" の形の時
Seq(s, i) = a
s = "(" + Ｘ + B + □ + a + ")" の形の時
Seq(s, 0) = "(" + a + ")"
Seq(s, i+1) = "(" + Ｘ + Seq(B, i+1) + Seq(s, i) + □ + ")"
ただし、
s, a, b, B ∈ Ｔ ただし、B ≠ 0
□ : 0個以上の0を有限個繋げたもの
Ｘ : 0個以上のＴの元を有限個繋げたもの
i ∈ Ｎ
0344ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/08(土) 02:45:00○定義
a ∈ Ｔ とし、H[a] で Ｎ => Ｎ の関数を表し以下を満たす
H[0](n) = n+1
H[A](n) = H[Seq(A, n)](n+1)
ただし、
A ∈ Ｔ, A ≠ 0
0345ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/08(土) 02:45:37(1) = ((0))
(2) = (((0)))
(3) = ((((0))))
(i,j) = (i)(i)(i)…j+1個…(i)
0^i = 000...i個…0
【Seq の計算】
Seq((0), i) = 0
Seq((n), i) = (n-1)
Seq(((n+1,1)), i+1) = (Seq((n+1), i+1) + Seq(((n+1,1)), i))
= ((n) + Seq(((n+1,1)), i))
= ((n, i) + Seq(((n+1,1)), 0))
= ((n, i) + (n+1))
Seq(((n+1,m+2)), i+1) = ((n+1,m) + Seq((n+1), i+1) + Seq(((n+1,1)), i))
= ((n+1,m) + (n, i) + (n+1))
Seq(((n+1) + 0), i+1) = (Seq((n+1), i+1) + Seq(((n+1) + 0), i))
= ((n) + Seq(((n+1) + 0), i))
= ((n, i) + Seq(((n+1) + 0), 0))
= ((n, i) + 0)
Seq(((n+1, m+2) + 0), i+1) = ((n+1,m) + Seq((n+1), i+1) + Seq(((n+1) + 0), i))
= ((n+1,m) + (n, i) + 0)
Seq((0, m+2) + 0, i+1) = ((0,m) + Seq((0), i+1) + Seq(((0, m+2) + 0), i))
= ((0,m) + 0 + Seq(((0, m+2) + 0), i))
= ((0,m) + 0^(i+2))
0346ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/08(土) 02:47:25H[((((0)))0)](n) = H[((2)0)](n) = H[Seq(((2)0), n)](n+1)
= H[((1, n-1) + 0)](n+1)
= H[Seq(((1, n-1) + 0), n+1)](n+2)
= H[((1, n-3) + (0, n) + 0)](n+2)
= H[Seq(((1, n-3) + (0, n) + 0), n+2)](n+3)
= H[((1, n-3) + (0, n-2) + 0^(n+3))](n+3)
= H[Seq(((1, n-3) + (0, n-2) + 0^(n+3)), n+3)](n+4)
Seq((X + (0, n-2) + 0^(n+3)), n+3)
= (X + (0, n-3) + Seq((0), n+3) + Seq((X + (0, n-2) + 0^(n+3)), n+2) + 0^(n+2))
= (X + (0, n-3) + 0 + Seq((X + (0, n-2) + 0^(n+3)), n+2) + 0^(n+2))
普通に計算したのでは、歯が立たないかな。
また、改めて出直してきます。
0347たろう
2007/09/08(土) 07:44:37http://web.mit.edu/dmytro/www/other/OrdinalNotation.htm
順序数の生成にはこれを参考にしたC0を使っています。
（Cの一番小さいものを多変数にしたもの）
veblen関数の多変数に比べて変数１個分小さいですが、
その分、加算の定義が不要となります。
-----------C0-----------
●定義
C0(□, a) = a+1
C0(Ｘ, b+1, a) = lim { 初項 a / ２項目以降 C0(Ｘ, b, １個前の項) }
C0(Ｘ, b+1, 0, □, a) = lim { 初項 a / ２項目以降 C0(Ｘ, b, １個前の項, □, a) }
C0(Ｘ, B, □, a) = lim C0(Ｘ, B_n, □, a)
ただし、
a, b : 順序数
A, B : 極限順序数 （A_n, B_n : 収束列）
□ : 0個以上の0
Ｘ : 0個以上の0以上の順序数
●大きさ
C0(a) = a+1
C0(a,0) = ω^a
C0(1,0,0) = ε_0
C0(2,0,0) = η_0
C0(1,0,0,0) = Γ_0
C0(1,0,0,0) = Γ_Γ_...Γ_0
C0(2,0,0,0) = ψ(Ω^2)
C0(1,0,0,0,0) = ψ(Ω^3)
lim C0(1,0,0,....n個.....,0,0) = ψ(Ω^ω)
0348たろう
2007/09/08(土) 07:53:24"0" => 0
"(0)" => 1
"((0))" => 2
"(((0)))" => 3
"((0)0)" => C0(1,0) => ω
"(((0))0)" => C0(2,0) => ω^2
"((0)00)" => C0(C0(0),0,0) => ε_0
"((0)000)" => C0(C0(0),0,0,0,0) => Γ_0
Seq(s, i) は、順序数が極限の場合はその収束列を返し、
順序数がa+1の形の場合はaを返します。
H[a] はaが後続順序数と極限順序数の時の定義をくっつけた
ハーディー関数になります。
0349１３２人目の素数さん
2007/09/08(土) 07:59:56H[((((0))0)0)] = H[ω^ω^2] ≒ F[ω^2](n)
H[((((0)0)0)0)] = H[ω^ω^ω] ≒ F[ω^ω](n)
0350たろう
2007/09/08(土) 08:06:53× "((0)000)" => C0(C0(0),0,0,0,0) => Γ_0
○ "((0)000)" => C0(C0(0),0,0,0) => Γ_0
ミスが多くてすいません。
Seq の定義は、定義式の数を減らすため、>>347 の定義と微妙に変えてあります。
0351ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/09(日) 01:17:49> Seq の定義は、定義式の数を減らすため、>>347 の定義と微妙に変えてあります。
C0(Ｘ, B, □, a) = lim { 初項 a / 2項目以降 C0(X, B_n, 1個前の項, □) }
といった感じですか？
どうしてこれが順序数の収束列になるのかがまだよく分かりませんが、
もう少しよく考えてみます。
0352１３２人目の素数さん
2007/09/09(日) 22:45:32F_ω^ω(x)はx重帰納的関数に相当するとたいていのHardy functionに
関する論文には書いてあるようです。x重帰納的関数は詳しくは知りませんが
たしか前スレにそれらしいものが載ってたと思います。
このようなこともあってF_ε_0(x)に相当する関数を順序数なしで定義するのは
不可能だと思っていたのですがふぃっしゅ数ver5がそれに到達している
というのは本当でしょうか？
Snakeやver5はまだ理解していないので理解できたらそれらとHardyの比較も
やりたいと思っています。
0353ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/10(月) 01:39:12ふぃっしゅ数ver5がF[ε_0](n)に達しているかどうかは、
よく分かりません。>>292では、達しているとされていますが、
その計算内容が十分にまだ分かっていません。
「F[ω^ω](x)はx重帰納的関数に相当する」ということから
「F[ε_0](x)に相当する関数を順序数なしで定義するのは不可能」
という帰結になるのはなぜでしょうか？「x重帰納的関数よりも
大きな関数は順序数なしでは定義できない」というようなことでも
あるのでしょうか？
「定義できない」ということが、もしも「TMで構成できない」と
いうことになればF[ε_0](x)がBB級の大きさになる可能性もありますが、
そんなことはないですよね。Hardy関数が計算可能である、という
ことに関しては特に問題ないようですし。
逆に、F[ε_0](x)等のHardy関数をTMで構成できるのであれば、
それはつまり帰納的に定義できるという意味だと感じますが、
甘いでしょうか。
Provably recursive という言葉も出てきましたが、そのあたりの
言葉との関係でしょうか…。
0354１３２人目の素数さん
2007/09/10(月) 17:28:44>>352
よく考えたら順序数と対応付けられる集合とかリストとかを
しらみつぶしに禁止するつもりですか？
Peano Arithmeticの中では任意のm(x)を構成することが
不可能ってことになるんじゃないでしょうか。
0355ルート41
2007/09/10(月) 18:59:48僕が前から考えていた巨大数の表記方法を失礼ながら書かせてもらいます。
Ａ～・Ｂという表記をするんですが、（～・で一つの記号です）定義として
Ａ～・1＝Ａ
Ａ～・2＝Ａ＾Ａ
Ａ～・3＝Ａ↑↑Ａ
Ａ～・4＝Ａ→→Ａ
としています。つまり、～・の後の数字が一つ増えるごとに→→と同じこと
前の記号に行うという事です。
次にＡ～・～・Ｂ＝Ａ～・（Ａ～・Ｂ）と定義します。
次にａｂｃｄの自然数において
ｎ＝ａ～・ｂ＞（ａ＾ｂ）～・（ｃ＾ｄ）＞ｂ＞ｄ＞ｃ＞ａ
が成り立つ時のｎの最小数を◎と表示します。
～・だとふた文字に見えるので♪を代用します。
◎♪♪♪♪♪♪♪♪◎という表記は10文字以内では大きい表示になるんでしょうか？
0356１３２人目の素数さん
2007/09/10(月) 20:08:540357ルート41
2007/09/10(月) 20:19:23Ａ～・Ｂの表記のＢは何種類目の記号が使われたかを表しています。
Ｂ＝100なら100種類目の記号という意味です。巨大数を表す場合、
なんらかの記号を使って標記すので、最終的にはその記号の数を数える
のが最も大きな数になるという考えから～・を考案したのです。
ただこのままだと、ほとんど反則なので＞＞355では一番解りやすい
→→の法則で次の記号を定義しました。（もともとＡ～・Ｂは絶対
に表記出来ない数がある事の証明で作ったので、Ｂ＝100なら100種類
の記号を必ず使います） 説明下手ですいません。
あと途中の式ですが、これは
ａｂｃｄの自然数において
ｎ＝ａ→→ｂ＞（ａ＾ｂ）→→（ｃ＾ｄ）＞ｂ＞ｄ＞ｃ＞ａ
が成り立つ時のｎは少なくとも3→→1025より大きい数のとき
であるの応用で作りました（ｎの最小値がいくらは、僕にわ
解らないです。誰か計算できるひといませんかね）
0358ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/10(月) 20:48:34F[φ_ω(0)](n)やF[ψ(Ω^(Ω+ω))](n)がいとも簡単にコーディング
されていますが、このプログラムを理解できる人はいますか？
おそらく、基本的には>>347のアイデアを使っているのだと
思います。私としては、順序数の収束列をこのように多重帰納
関数の様な形で定義できる、ということが驚きで、いまだ理解に
至っていないのですが…。
http://web.mit.edu/dmytro/www/other/OrdinalNotation.htm
こちらのページを見ても、C(Ｘ, B, □, a)を導く一般式、のような
ものは書かれていないように見えますし。やはり、なぜ>>347の
式で順序数の収束列を定義できるか、という点については解説
していただかないと、私だけではなく皆さん理解できないのでは
ないでしょうか？
0359ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/10(月) 20:59:32http://www.geocities.co.jp/Technopolis/9946/log/ln051.html
ここの58で、m(3)がF(x,y,z)=F(x-1,F(x,y-1,z),F(x,y-1,z)) で
あらわされました。この関数が真の三重帰納か、それとも実は
二重帰納か、という議論があったとは思いますが、いずれにしても、
m(n)は良くて多重帰納、もしかすると二重帰納になる気がします。
F[ε_0](n)になるというのは、落ち着いて考えると過大評価しすぎ
なような…。
また、m(3)が三重帰納であれば、s(n)はm(3)で生成される程度の
関数ですから、それよりも小さく、二重帰納程度です。
0360ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/10(月) 21:00:03であることが分かっているので、いずれも二重帰納で、
m(n)が多重帰納であるとすれば、
Knuthの上矢印 3(↑^n)3 ≒ F[ω](n)
Ak(n, 3) ≒ F[ω](n)
ふぃっしゅ数バージョン1のSS変換：F[ω^2](n)
n個のnからなるConwayのチェーン ≒ F[ω^2](n)
ふぃっしゅ数バージョン2のSS変換：F[ω^2](n)
チェーンの回転 ↑n (3,3,3) ≒ F[ω^2](n)
バード数の定義の X_n(a) の入れ子操作n回 ≒ F[ω^2](n)
ふぃっしゅ数バージョン3のs(n)変換：F[ω^2](n)
ふぃっしゅ数バージョン５のm(3) ≒ F[ω^3](n)
真の三重帰納関数 ≒ F[ω^3](n)
例: A(x+1,y+1,z+1) = A(x,A(x+1,y,A(x+1,y+1,z)),A(x+1,y+1,z)))
真の四重帰納関数 ≒ F[ω^4](n)
例: A(w+1,x+1,y+1,z+1)=
A(w,A(w+1,x,A(w+1,x+1,y,A(w+1,x+1,y+1,z)),A(w+1,x+1,y+1,z)),A(w+1,x+1,y,A(w+1,x+1,y+1,z)),A(w+1,x+1,y+1,z))
真のn重帰納関数 ≒ F[ω^ω](n)
ふぃっしゅ数バージョン５のf5(n) ≒ F[ω^ω](n)
こんな感じになるのではないでしょうか。
0361ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/10(月) 21:01:03真の○重帰納関数以外は、すべてF[ω^2](n)でした、という話に
なると思います。
>>311が正しいのか、それとも本当は>>360のような感じなのか。
そして、それはHardy関数を正確に計算することではっきりする
ものなのか。
Hardy で関数の大きさが整理できるといっても、正確に計算
しようとするとけっこう大変ですね。
0362ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/10(月) 21:50:11議論の雰囲気を読むと、Hardy + 順序数による巨大数の定義は、
canonical sequence の取り方が１つに保証されないε_0以上の
世界は、関数が１つに定まるかどうか不明という点で、きっちりと
定義された関数、あるいは数の仲間入りをさせていいかどうかと
いう疑問がまだ残っています。
そんなこんなで色々と昔を思い出していると、やはり多重帰納は
強力なので、なんとかして多重帰納を本質的に強める方法はないか、
と考えてしまうわけですが…。
http://www.geocities.co.jp/Technopolis/9946/log/ln051.html
ここの184によって、n重帰納関数 A_n(a_n,...,a_1) を定義する。
ただし、A_1(x)=f(x)、g(x)=A_x(a_x,...,a_1)とすることで、
関数 f(x) から 関数 g(x) への写像が定義される。
この写像は、f(x)=x+1という関数をF[ω^ω]クラスに持って行く
だけの力を持った写像である。
この時に、生成された多重帰納関数に対してこの写像の適用を
繰り返すとどうなるか。
0363ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/10(月) 21:51:37(1) F[ω^ω] のまま変わらない
(2) F[ω^(ω+1)], F[ω^(ω+2)], ... F[ω^(ω*2)]
(3) F[ω^(ω*2)], F[ω^(ω*3)], ... F[ω^(ω^2)]
(4) F[ω^(ω^2)], F[ω^(ω^3)], ... F[ω^ω^ω]
(5) F[ω^ω], F[ω^ω^ω)], ... F[ε_0]
良くて(3)あたりだと思うのですが…どうでしょう。
この写像をM2変換としたふぃっしゅ数V5を考えたところで、
F[ε_0] までは到底到達しない…のでしょうね。本質的に強める
ためには、更なる工夫が必要かな。
0364ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/10(月) 23:29:14> ただし、A_1(x)=f(x)、g(x)=A_x(a_x,...,a_1)とすることで、
ただし、A_1(x)=f(x)、g(x)=A_x(x,x,...,x)とすることで、
でした。
0365１３２人目の素数さん
2007/09/11(火) 06:44:31すいません、書き方がまずかったです。
Hardy Functionはもちろん計算可能ですのでもちろんF[ε_0](x)はBB以下になります。
単にPAではProvably recursiveでない最小のものということですね。
過去スレに（一般的な？）多重帰納関数の例がでてきたときに順序数なしでは
これが最強だと思っていたのでF[ε_0](x)レベルのものは無理なんじゃないかと
勝手に思っていたので、ふぃっしゅ関数ver5がこれに至っているということに懐疑的に
なっていました。
しかし、ふぃっしゅ関数ver5がF[ω^ω](x)（＝H[ω^ω^ω](x)）に至っているというだけ
でも個人的にはすごいことだと思います。
>>362
＞ε_0以上の世界は、関数が１つに定まるかどうか不明
http://www.geocities.co.jp/Technopolis/9946/log/thread6.html
ここの>>655に定義の例が書かれています。
0366366
2007/09/11(火) 19:36:390367ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/11(火) 20:53:22このスレッドを読み直しているところですが、ふぃっしゅ数バージョン５
(F5)は多重帰納関数以上、ということでどうやら良さそうです。
まず、58の式はm(3)1回で生成されるs(1)に相当するm(2)がアッカーマン
であることを示している式です。それは当たり前のことで、
>>359のようにm(n)が二重帰納ということにはならないわけですが、
そのあたりで本人が錯誤をしていました。
m(n)の威力はm(3)からではなくm(4)からはじまりますが、
m(4)の計算をした63を見ただけでは、まだ2重帰納か多重帰納かは
よく分からない。
0368ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/11(火) 20:54:413重帰納関数
f(x+1,y+1,z+1) = f(x,f(x+1,y,f(x+1,y+1,z)),f(x+1,y+1,z)))
が3重帰納である所以は、
f(x+1,y+1,z+1) が 3-term でそのなかに現われる f は
f(x,*,*), f(x+1,y,*), f(x+1,y+1,z) という形であり、
ただし、f(0,y,z) はこの定義で 2-term の形で定義される。
ということです。ここで、f(x,*,*), f(x+1,y,*), f(x+1,y+1,z) とは
(1) f(x,*,*) の * に f(x+1,y,*) を入れる
→ f(x,f(x+1,y,*),f(x+1,y,*))
(2) この式の * に f(x+1,y+1,z) を入れる
→ f(x,f(x+1,y,f(x+1,y+1,z)),f(x+1,y+1,z)))
という意味です。
0369ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/11(火) 20:59:50それは、157に書かれている通り、
f(x,*,*), f(x+1,y,*), f(x+1,y+1,z) からxを落とすと
f(y,*), f(y+1,z) 、すなわち f(y, f(y+1,z)) の2重帰納が出てくる。
つまり、f(x,y,z) は、xを1つ増加させる毎に、y,zに関する
2重帰納をしている。したがって、2重帰納を有限回(n回)施して
得られるどんな2重帰納関数よりも、x>nの時点で大きくなるが
ために、3重帰納関数はいかなる2重帰納関数よりも大きくなります。
これは、アッカーマン関数がいかなる原始帰納関数よりも大きい
ことの説明と同じで、アッカーマン関数が原始帰納関数を枚挙
するがごとく、3重帰納関数が2重帰納関数を「枚挙している」
ということです。
Hardy 関数では、2重帰納の操作 ω^2 を枚挙することで、
ω^2, ω^2+ω^2, ω^2+ω^2+ω^2, ..., ω^3
の収束列が得られる、ということに相当するのでしょう。
0370ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/11(火) 21:03:54そこで、あらためて自分が書いた 146-147 を読み直してみると、
どうやらそんなに間違ったことを書いてないです。
s(2)が2重帰納である、というところまでは良しとして
(F5のs(n)はF3のs(n-1)に相当する)、この説明の中でキーと
なるのは、「s(3)が2重帰納の操作を荒い意味で枚挙する」
という表現です。
s(3)の定義は
s(3)f(x)=(s(2)^x)f(x)
となりますが、
s2(n,x)=(s(2)^n)f(x)
と書いた時に、s(2)は2重帰納の操作をあらわしているので、
2重帰帰納をm回施して得られるどんな2重帰納関数よりも、
n>mの時点で大きくなります。このように、s2(x,x)は
2重帰納を枚挙する3重帰納となります。
したがって、s(3)は3重帰納の操作となります。
そうすると、s(n)は同様にn重帰納となります。
いやはや、皆様（分かる人には）分かっていたことを、
ようやくもって本人が理解できた、というところでしょうか。
0371ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/11(火) 21:06:02>>311の前半にふぃっしゅ数Fを加えて
Knuthの上矢印 3(↑^n)3 ≒ F[ω](n)
Ak(n, 3) ≒ F[ω](n)
n個のnからなるConwayのチェーン ≒ F[ω^2](n)
F5のm(2)n回 ≒ F5のs(1)n回 ≒ F[ω^2](n)
チェーンの回転 ↑n (3,3,3) ≒ F[ω^3](n)
F5のs(2)n回 ≒ F3のs(1)n回 ≒ F1,F2のS変換n回 ≒ F[ω^3](n)
バード数の定義の X_n(a) の入れ子操作n回 ≒ F[ω^3+ω+1](n)
F5のs(3)n回 ≒ F3のs(2)n回 ≒ F2のSS変換n回 ≒ F[ω^4](n)
5変数Ak ≒ F[ω^4](n)
多変数Ak Ak(n個のn) ≒ F[ω^ω](n)
F5のs(n) ≒ F3のs(n) ≒ F[ω^ω](n)
F5のm(4) = F5のm(3)n回 ≒ F[ω^ω](n)
ここまでは理解できました。
0372ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/11(火) 21:14:50ふぃっしゅ数考案者の希望的観測としては、>>292のように
Ak を２重リストに拡張、Ak([n個のn], [n]) ≒ F[ω^ω^ω](n)
F5のm(5) ≒ F[ω^ω^ω](n)
F5のm(6) ≒ F[ω^ω^ω^ω](n)
F5のf5(n) ≒ F[ε_0](n)
となればいいかな、と思いますが、はたしてそうなるかどうか。
考案した本人も、その大きさを評価できずにいます。
0373ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/11(火) 21:33:46なるほど。スレッド6の655におけるα<Γ_0 が φ_β(γ) (β,γ<α)の
定義を見ると、このような形できれいに記述できるのであれば、
>>347-350のように順序数の定義を帰納的に記述できて、
http://web.mit.edu/dmytro/www/other/OrdinalNotation.htm
ここのordinal, stronger ordinal といった表現を簡潔に与える
ことができるとしても、不思議はないような気がしてきました。
とはいえ、>>338のプログラムを見ると、本当にこんなに短い
プログラムでF[ψ(Ω^(Ω+ω))](n) を生成できるのかと、驚くばかり
ですが。それが、計算可能の意味するところといえばそうですね。
0374ルート41
2007/09/12(水) 20:26:43ＢＢ関数の定義が計算出来るどんな関数より大きな関数という事
らしんですが。無限大に増加する関数以外は全て計算出来る関数
だとしたＢＢ関数は存在しない関数、もしくは大きい事が証明出
来ない関数になると思うんですが。
実際のところＢＢ関数はそこらへんの事はどうｸﾘｱｰしてるんですか？
0375ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/12(水) 21:33:18> 無限大に増加する関数以外は全て計算出来る関数
無限大に増加する関数y=xは計算できます。
「ある値を代入したときに無限大になる」という
意味でしょうか？だとしたら、BB関数の値は有限
ですが有限時間内に計算できません。
> ＢＢ関数は存在しない関数
BB関数は存在します。しかし、その値を有限時間内に
計算ができません。
> 大きい事が証明出来ない関数
「あらゆる計算可能な関数よりも大きい」という
「大きい事」に関しては、証明ができます。
「どのくらい大きいか」を具体的に計算は出来ません。
さて、
自分の中で、曖昧だった多重帰納の概念がようやくはっきり
したので、これまでのまとめの文章を作ろうと考えていますが、
しっかり作るとかなりの大作になりそう…。
その次の段階ですが、ハーディーを使って、バージョン5よりも
大きな関数がどんどん構成されるようになってきたので、
いよいよバージョン6を考えてみようかという気にもなって
きました。ふぃっしゅ数の特徴である高階集合の定義で、
ハーディーでいうところのどのあたりまで到達できるだ
ろうか、というのが目標です。
0376ルート41
2007/09/12(水) 22:21:43無限大に増加する関数とは、例えばｆ（0）＝0 Ｆ（1）＝1 ｆ（2）＝∞
という意味で書きました。極端にすればｆ（0）＝0 ｆ（極限に小さい数）＝∞
僕的には∞＝∞＾∞＝∞↑↑∞と考え、∞になるものは大小の比較は出来ないと
考えていたもので。
ＢＢ関数の定義は有限時間で計算すると理解します（あと、人間の能力で
も入るかもしれませんが）
0377ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/12(水) 23:32:11ただし、定義によって有限の数が定まる事が保証されています。
人間の能力は無関係です。
ここから先は、BBの定義そのものを理解しないとどうしようも
ないといえばないのですが、たとえばBB(10)を計算したいとします。
定義にしたがって計算すると、BB(10)の値となる候補が次々と
計算されます。その候補の値は、計算時間がたてばたつほど
大きくなります。真の値BB(10)は必ず存在しますので、
その値に到達する時も来るでしょう。ただ、その計算された値が
BB(10)であるという保証が出ません。保証が出ないという事は、
計算が終了しないということです。計算時間が増えるにつれて、
どんどん候補の値が大きくなるけれど、どこで「本当のBB(10)」
に到達したかを知り得ることができないので、有限時間内に
計算が終了しない、つまり計算できない、ということになります。
0378１３２人目の素数さん
2007/09/13(木) 00:33:55過去スレを見ても何度も変更されているし、途中で話がそれてしまっていて
わからないのですが・・・
0379ルート41
2007/09/13(木) 18:23:59ＢＢ関数が存在するという事は今の所理解出来ませんが、僕がＢＢ関数を
理解してないという事は理解しました。（ＢＢ関数の公式てあるのかな？）
ちなみに＞＞376の様になる関数には
Ｙ＝Ｎ＾∞や Ｙ＝Ｎ＾Ｙ（Ｎ≠1なら単に成り立たないともいえるが）
が有ります。
あと、ふぃっしゅ数については、僕はまだ理解していませんが、存在して
いる事はわかります。
0380ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/13(木) 19:46:14そうですね、まずはふぃっしゅ数ver.5の定義をはっきりさせる
ところからはじめようと思います。おおまかな原案は書きましたが、
きちんとこれが定義だという形にはまだしていなかったので。
ちょうどその頃に、色々な議論があってうやむやになってしまって
いました。
>>379
BB関数は、計算理論の勉強をしないと理解できません。
計算理論の専門書を読んで理解するのが、一番いいのだと思います。
私は、英語のホームページを読んで理解しましたが、日本語の
ホームページで分かりやすく解説してあるところは、はたして
あるかどうか。
0381ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/13(木) 19:59:46http://en.wikipedia.org/wiki/Busy_beaver
ここの2-state S(n,m)の値を見ると、
BB(2) = 6
BB(3) = 21
BB(4) = 107
BB(5) ≥ 47,176,870
BB(6) ≥ 3.0 x 10^1730
となっています。BB(4)までは「=」で、正確な値が分かって
います。BB(5)以降は「≥」となっています。つまり、
BB(5)の値は47,176,870 かもしれないし、それよりも
大きいかもしれない。
我々は、まだBB(5)の正確な値を知り得ていない、という
ことになります。BB(6)の正確な値は、どんなに計算機の
速度が向上しても、どんなに長い年月をかけても
（たとえばふぃっしゅ数年とか）、計算できないでしょう。
0382ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/13(木) 20:09:03方でしたね。訂正しておきます。
BB(2) = 4
BB(3) = 6
BB(4) = 13
BB(5) ≥ 4098
BB(6) ≥ 1.2 x 10^865
0383ルート41
2007/09/13(木) 20:28:13丁寧な解答ありがとうございます。
0384たろう
2007/09/13(木) 20:35:35ビジービーバー関数とは、プログラムn文字で作り出せる最大の数。（※）
だからプログラムで書けるどんな関数よりも増大度が大きい。
※実際はBBはチューリングマシンという非常に単純なマシンでの定義となる
ただ、
すべての値に対してBB(n)を返すプログラムがかけないというだけであって、
BB(10)やBB(100)を返すプログラムの存在を否定するものではない。
0385たろう
2007/09/13(木) 20:49:16微妙にちがう。初項は a+1。
----- >>338 のプログラムの解説 ------
>>266 のプログラムを色々変えて小さくしたもの。
117語のものは、C0の変数を３つに限定し、一番左のは整数に限定したもので順序数を作り出している
132語のものは、C0を多変数のまま使っている。
（コメントに F[ψ(Ω^(Ω+ω))](n) と書いてあるのはF[ψ(Ω^ω)](n) の間違い）
プログラムでは F[ψ(Ω^ω)](9) 程度の数を返すが、
プログラム上の数値のいくつかを変えることで 9 を大きく出来る。
○小さくする工夫
φよりも定義が簡単で加算の定義も不要なC0を用いている
ハーディー関数を再帰ではなくループで表現している
F[ψ(Ω^ω)](9) = F[ψ(Ω^9)](9) なので、F[ψ(Ω^9)](9) を計算している
収束列を微妙に変えている
C言語上の色々な工夫でサイズを小さくしている
など
0387たろう
2007/09/13(木) 21:04:29ふぃっしゅ数V5のm(5)の大きさは力ずくでもわかる。
（m(2) = m2, m(3) = m3, m(4) = m4, ...）
aは自然数
m2 ===> +1 （f ≒ F[a] の時、 m2 f ≒ F[a+1] という意味）
m2 m2 ===> +2 （f ≒ F[a] の時、 m2 f ≒ F[a+2] という意味）
m2^a ===> +a
m3 m2 ===> +ω
m3 m2 m3 m2 ===> +ω*2
m3 m2 m3 m2 m3 m2 ===> +ω*3
(m3 m2)^a ===> ω*a
m3 m3 m2 ===> ω^2
m3 m3 m3 m2 ===> ω^3
m3^a m2 ===> ω^a
m4 m3 m2 ===> ω^ω
m3 m4 m3 m2 ===> ω^ω*ω
m3 m3 m4 m3 m2 ===> ω^ω*ω^2
m3^a m4 m3 m2 ===> ω^ω*ω^a
m4 m3 m4 m3 m2 ===> ω^(ω*2)
(m4 m3)^a m2 ===> ω^(ω*a)
(m4 m3)^a m2 ===> ω^(ω*a)
m4 m4 m3 m2 ===> ω^ω^2
0388１３２人目の素数さん
2007/09/13(木) 21:05:21(m4 m3)^a m2 ===> ω^(ω*a)
m4 m4 m3 m2 ===> ω^ω^2
m3 m4 m4 m3 m2 ===> ω＾(ω^2+1)
m3^a m4 m4 m3 m2 ===> ω^(ω^2+a)
m4 m3 m4 m4 m3 m2 ===> ω^(ω^2+ω)
m4 m4 m3 m4 m4 m3 m2 ===> ω^(ω^2*2)
(m4 m4 m3)^a m2 ===> ω^(ω^2*a)
m4 m4 m4 m3 m2 ===> ω^ω^3
m4^a m3 m2 ===> ω^ω^a
m5 m4 m3 m2 ===> ω^ω^ω
0389たろう
2007/09/13(木) 21:33:42ここのたろう的理解です。
●C0
[A General Notation] のCのΩ導入前を多変数化
C0(..., a5, a4, a3, a2, a1, a0) = C(..., Ω^4 * a5 + Ω^3 * a4 + Ω^2 * a3 + Ω * a2 + a1, a0)
C0(..., a4, a3, a2, 0, 0) = φ(..., a4, a3, a2, 0)
>>190 のψ(Ω^ω) 未満の順序数をすべて表現可能。
●C1
[An Ordinal NOtation] の多変数化
C1(1,0,0) を、帰納的でない最小の順序数、
C1(2,0,0) を、C1(1,0,0) と帰納的定義で表現できない最小の順序数、
......
C1(1,0,0,0) を、C1(a2, 0, 0) と帰納的定義で表現できない最小の順序数、
....
というような解釈で良いかと。
C1([C1で生成される順序数], 0) は帰納的な順序数となる。
C1(1,0,0) は 上のΩや >>190 のΩとほぼ同じ意味。
C1(C1(1,0,0),0) = C0(1,0,0)
C1(C1(1,0,0)^2,0) = C0(1,0,0,0)
C1(C1(1,0,0)^3,0) = C0(1,0,0,0,0)
>>202 のψ_a(0) が C1(a,0,0) とほぼ同じ意味。
３変数で >>202 の ψ_0(Ψ) 未満の順序数をすべて表現可能。
0390１３２人目の素数さん
2007/09/13(木) 21:38:44[Beyond Second Order Arithmetic] の C の多変数化
C0 => C1 の進化を繰り返したもの。
C2(C2(1,0,0),0) = C1(1,0,0)
C2(C2(1,0,0)^2,0) = C1(1,0,0,0)
C2(C2(1,0,0)^3,0) = C1(1,0,0,0,0)
C2([C2で作り出す順序数], 0) はC1でつくり出せる順序数となり、
C2(C2([C2で作り出す順序数], 0)) で帰納的な順序数となる。
0391たろう
2007/09/13(木) 21:51:46多変数veblen ＋ 加算 と同等の表現が可能。
C1 の収束列は、>>202 のような方法で定義できる。
だいたい８個くらいに場合分けした定義となる。
３変数で、veblen ＋ 添字付ψ ＋ 加算 と同等の表現か可能。
プログラムで書けば、>>266よりずいぶん小さくできそう。
C2 の収束列はかなり複雑で途中で挫折。
C3, C4.... と拡張できそうな気がする。
さらには、C_n(c, b, a) ==> C_[順序数](c, b, a) ==> C(d, c, b, a) => 多変数化 => さらに大きなΩでの表現 => ...
でも、順序数の専門家がもっと大きな帰納的順序数を見つけてそう。
0392たろう
2007/09/13(木) 21:56:14> C2([C2で作り出す順序数], 0) はC1でつくり出せる順序数となり、
ここは間違いで、以下に訂正。
C2([C2で作り出す順序数], 0) はC2(1,0,0) 未満の順序数となり、
0394ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/14(金) 01:54:20その定義を見ていると、ナゴヤ数(スレッド6の510-511)も
どこかのクラスに入りそうですね。
まだ、雰囲気だけしかつかめませんが。
0395たろう
2007/09/14(金) 19:46:19まだまちがってた。
C2([C2で作り出す順序数], 0) はC2(1,0,0) 未満の順序数となり、
C2(C2([C2で作り出す順序数], 0),0) で帰納的な順序数となる。
>>394
>>135 が正しければ大きさは、
多変数veblenの極限 = ψ(Ω^ω) = C0の極限 = C1(C1(1,0,0)^ω, 0) 程度
>>125 のveblenの極限はψ(Ω^Ω) = C1(C1(1,0,0)^C1(1,0,0), 0)
同じように拡張していきn重リストにするとその極限は、ψ(ε_(Ω+1)) となって
Howard ordinal に到達。
0396ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/14(金) 20:18:53[1] 集合Mn (n=0,1,2,...)を以下のように定める。
M0=自然数の集合
M{n+1}=写像Mn→Mn全体の集合
Mnの元をMn変換と呼ぶ
[2] Mn変換 m(n) (n≧1) を以下のように定める。
f_n∈M(n)に対して、m(n+1)(f_n)=g_nを以下で定める。
f_{n-1}∈M(n-1)に対して、g_n(f_{n-1})=g_{n-1}を以下で定める。
f_{n-2}∈M(n-2)に対して、g_{n-1}(f_{n-2})=g_{n-2}を以下で定める。
……
f_0∈M(0)に対して、g_1(f_0)=g_0を以下で定める。
g_0=(..((f_n^{f_0}f_{n-1})f_{n-2})...f_1)f_0
すなわち
m(1)(f_0)=f_0^f_0
(m(2)f_1)f_0=(f_1^f_0)(f_0)
(..((m(n+1)f_n)f_{n-1})...f_1)f_0:=(..(f_n^{f_0}f_{n-1})...f_1)f_0
[3] ふぃっしゅ関数 F5(x) を以下のように定める。
F5(x):=((..((m(x)m(x-1))m(x-2))...m(2))m(1))(x)
[4] ふぃっしゅ数 F5:=F5^63(3) とする。
0397ルート41
2007/09/14(金) 20:25:12僕の作った式に解答ありがとうございます。
～・Ｎの定義はＮ×Ｎ＜Ｎ～Ｎ＜Ｎ↑↑ＮならＮが増える毎に表記方法も上位の物を使用して
行く関数を作れば大きな関数を作れると考えて作りました。
よく考えればＮ＾ＮからＮ↑↑Ｎへ変化するのとＮ↑↑ＮからＮ→→Ｎに変化するのは
意味が違うため関数としてはなりたったなかったですね。
考えてる途中にＮ＝1なら1 Ｎ＝2なら22 Ｎ＝3なら333×333 Ｎ＝4なら4444＾4444
にしないといけないかと思ったくらいですから。
（見た目が面白いので1.22.333となる関数を作ろうとしているんですが上手くいかないですね。）
◎を導く式のほうは、大きくなる関数を作る事を、ある巨大数を入れないと成り立たない式を作る
ことで抜けないか考えて挫折したときの残骸です。＞＞357の→の方が実際に作っやつですが。
それでもＡ→→ＢにおいてＢの数が大きいほうがＡの数が大きいときより大きな数になる事を
証明できれる最小の数であれば、グラハム数や現在最も大きい素数2＾32582657-1の様に
意味のある数として使えるかなと思い使いました。これもよく考えてみれば
Ｎ＝Ａ→→Ｂ＞Ｂ→→Ａ＞Ｂ＞Ａ
と書いた方が適切でしたね。
さらにＮ＝3→→4＞4→→3が成り立つことを正確に計算できても、グラハム数＞4→→3
が計算されたらグラハム数より大きい意味のある数にはならないですよね。
3→→4＞グラハム数は当たり前ですから。
もし↓や←を使った場合の計算が膨大すぎて、現在まだ正確な計算が出来ていないなら、
正確に計算することに意味が出てくるんでしょうが。
Ｎ＝Ａ＾Ｂ＞Ｂ＾Ａ＞Ｂ＞ＡならＮの最小値は32
Ｎ＝Ａ↑↑Ｂ＞Ｂ↑↑Ａ＞Ｂ＞ＡならＮの最小値は16
なら僕にも計算できるんですけどね。
僕の様な素人の書き込みでも、大きな数を見つけるヒントでも転がってれば良いんですが。
0398ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/14(金) 23:30:10それで気づいたのですが、今まではふぃっしゅ関数バージョン1 F1(x)
が2重帰納かと思っていましたが、違いました。3重帰納です。
F1(x) ≒ F[ω^3](x) (3重帰納)
なぜかというと、F1(x)は2重帰納のS変換を繰り返す回数が変数のx以上に
なるので、S変換をちゃんと数え上げているんですね。
一方、F2(x)は3重帰納のSS変換を63回繰り返しているので、
F2(x) ≒ F[63*ω^3](x) (3重帰納)
となります。F1(x)もF2(x)も、同じ3重帰納のクラスで、チェーンよりも
強くバードと同じ程度でした。
今まで、F1(x)の強さを過小評価していたようです。
0399たろう
2007/09/15(土) 00:23:14３重帰納 ≒ F[ω^2](n)
じゃないの？
F1(x), F2(x) の定義はどこにありますか？
0400たろう
2007/09/15(土) 00:41:46ここの >>320 で定義されているふぃっしゅ関数が F2(x) だとすると、
F2(x) ≒ F[ω*大きな整数](x) な気がする。
f(x) = x+1 に対してS変換を整数回行う操作を63回繰り返すだけですよね？
0401ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/15(土) 00:58:27F1(x)は2重帰納です。
>>399
そうでした。
F1(x) ≒ F[ω*大きな整数](x)
F1(x) ≒ F[ω^2*63](x)
です。
>>400
そちらはF1(x)の定義です。
F2(x)の定義は
http://www.geocities.co.jp/Technopolis/9946/log/ln032.html#R47
ここにありますが、F1(x)のSS変換の定義において、
S変換をx回繰り返すものです。
0402ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/15(土) 00:59:26F1(x) ≒ F[ω*大きな整数](x)
F2(x) ≒ F[ω^2*63](x)
0403ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/15(土) 03:05:56A(x+1,y+1,z+1) = A(x,A(x+1,y,A(x+1,y+1,z)),A(x+1,y+1,z)))
が3重帰納 F[ω^2] であることの証明
A(x+1,y+1,z) からAへの代入(合成)2回で A(x+1,y+1,z+1)ができる
→ zに+1する操作は合成の操作
Z=A(x+1,y+1,z)-a (Z > z+1) とすると、
f=A(x+1,y,Z) からg=A(x+1,y+1,Z)を合成と原始帰納で生成できる。
(1) Zをa増やす → A(x+1,y,A(x+1,y+1,z))
(2) A(x,y,A(x+1,y+1,z))のyに代入 → A(x+1,y+1,z+1)
(3) zをZ-(z+1)増やす (zを増やす操作を数え上げるので原始帰納)
したがって、yに+1するのは原始帰納
Y=A(x+1,y,Z)-bとすると、
f=A(x,Y,Z)からg=A(x+1,Y,Z)を3番目の引数を増やす原始帰納と
2番目の引数を増やす2重帰納で生成できるので、xへの+1は2重帰納
A(x,y,z)はxへの+1を数え上げるので3重帰納
0404１３２人目の素数さん
2007/09/15(土) 04:25:11日本大野菜協会が2002年に特別チームを発足し、5年の歳月を費やし、3ｍもの巨大サツマイモの栽培に成功した。
しかし、それが一般に発表される事はなかった。
その理由は栽培された巨大サツマイモがあまりにも男性器に酷似していたためである。
大野菜協会会長は「5年の歳月と沢山の経費をかけて作り出した大作といえるものだし、一般の方々にも見てもらいたい…が、ここまで酷似していてはコレを発表することは出来ない。我々にも恥がある。」
と、肩を落として語った。
長い歳月に渡り研究に研究を重ね、苦労の末栽培された世紀の大サツマイモは性器に似た大サツマイモになるという悲しい結末で幕を閉じた。
http://society6.2ch.net/test/read.cgi/river/1188899832/
0405たろう
2007/09/15(土) 07:18:19> A(x+1,y+1,z+1) = A(x,A(x+1,y,A(x+1,y+1,z)),A(x+1,y+1,z)))
3変数アッカーマン関数の定義はこれに決まってるの？
それとも、単なる拡張方法の１つ？
このスレでの合意？
単なる拡張方法の１つなら、
>>323 の方が簡単で良いと思うんだけど。
------アッカーマンの多変数への拡張の案------
●定義
Ak(□, a) = a+1
Ak(Ｘ, b+1, 0, □, a) = Ak(Ｘ, b, a, □, a)
Ak(Ｘ, b+1, 0) = Ak(Ｘ, b, 1)
Ak(Ｘ, b+1, a+1) = Ak(Ｘ, b, Ak(Ｘ, b+1, a))
ただし、
a, b : 0以上の整数
□ : 0個以上の0
Ｘ : 0個以上の0以上の整数
●大きさ
Ak(..., a2, a1, a0, n) ≒ F[...+ ω^2*a2 + ω*a1 + a0](n)
Ak(1がn個) ≒ F[ω^ω](n)
0406ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/15(土) 16:49:58多重帰納の定義については、
http://www.geocities.co.jp/Technopolis/9946/log/ln051.html
ここで色々議論されています。
76,77,155,181-184 あたりです。ここで提案されている
3変数アッカーマンについて検証したのが>>403で、2重帰納を
数え上げていることが分かりました。
>>323の方が簡単なので、これでω^2になっていればその方が
いいと思います。どういうしくみになっているのでしょう…。
0407ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/15(土) 17:30:30ack(x+1,y,z) = ack(x+1,0,z(y)) = ack(x,z(y),z(y))
とすると、z(y)が2重帰納関数になる。
なので、2重帰納をx回繰り返す3重帰納になる、ということか。
0408ふぃっしゅっしゅ ◆/T2GtW187g
2007/09/16(日) 00:04:09ちょっと書き方が変だったかな。
ack(x+1,y,z) ≒ ack(x+1,0,A(y,z)) ≒ ack(x,A(y,z),A(y,z))
といったところか。
>>405
この場合は
Ak(Ｘ, b+1, 0) = Ak(Ｘ, b, 1)
Ak(Ｘ, b+1, a+1) = Ak(Ｘ, b, Ak(Ｘ, b+1, a))
この箇所で、a0とnの計算について
Ak(..., a0, n) ≒ F[... + ω*a1 + a0](n)
という関係を作って、
Ak(Ｘ, b+1, 0, □, a) = Ak(Ｘ, b, a, □, a)
この箇所で、a=ak, b=a{k+1}として、
Ak(Ｘ, b+1, a, □, a) ≒ Ak(Ｘ, b+1, 0, □, F[ω^k])
= Ak(Ｘ, b, F[ω^k], □, F[ω^k])
≒ Ak(X, b-1, F[ω^k*2],...)
≒ Ak(X, b-2, F[ω^k*3],...)
...
≒ F[ω^(k+1)]
といった関係を作るわけですね。
0409ルート41
2007/09/16(日) 11:49:45（参照） http://ja.wikipedia.org/wiki/%CE%9C%E5%86%8D%E5%B8%B0%E9%96%A2%E6%95%B0
これは、
基本関数 N→→Ｎ＞Ｎ→Ｎ→Ｎ
次にバートの回転記号を○で表す
2○2＝2（2回転目←）（2回転目←）2
3○3＝3（3回転目←）（3回転目←）3
N○Ｎ＞Ｎ→→Ｎ
Ｎ○○Ｎ＞Ｎ○Ｎ○Ｎ
クラウ1 ステプ1
次に○の数を○ー○で表す（－は繋げること表しています）
2○ー○2＝2○○2
3○ー○3＝3○○○3
Ｎ○ー○ー○Ｎ＞Ｎ○ー○ ○ー○Ｎ
ステプ2
次に○ー○の繋がる数を○（＝）○で表す（＝はーの本数が2本の意味です）
2○（＝）○2＝2○ー○2
3○（＝）○3＝3○ー○ー○3
Ｎ○（Ξ）○Ｎ＞Ｎ○（＝）○（＝）○Ｎ
ステプ3
次に・・
0410ルート41
2007/09/16(日) 11:51:12クラス1のステプの数を（あ）で表す
2（あ）2＝2（＝）2
3（あ）3＝3（クラス1ステップ3の表記）3
Ｎ（い）Ｎ＞Ｎ（クラス1ステプＮの表記の（あ））Ｎ
ステプ2
（あ）から（い）の変化を（ド）で表す
（ド）の次は（レ）・・・
①ここでクラスの数を数える記号を作ればさらに巨大な関数が作れる
②更にステプ、クラス、（クラスを数える数）と段階が上がる事を数えると更に巨大な関数が作れる
このアルゴリズム（手順）を繰り返すことで大きな関数を作れる事が出来る。（①②を関数にして・・・）
このアルゴリズムその物を関数化した物みたいなんですが。この考えで行くと
①1帰納関数→2帰納関数→3帰納関数
②1重帰納関数→2重帰納関数→3重帰納関数
③1重帰納関数→2重重帰納関数→3重重重
④①→②→③をさらに関数にする。
このアルゴリズムその物を関数にする（その方法が全然判らないんですが）と、
ふぃっしゅ数バージョン5より大きな関数になると思うんですが？
それとも、ふぃっしゅう数ではμ作用素関数は折込済みなんですかね？
（この説明で伝わると良いんですが）
0411１３２人目の素数さん
2007/09/16(日) 19:11:17・ふぃっしゅ数はアッカーマン関数を折込済みです
そういえばアッカーマン関数を最小化を使って表すと
どうなるんでしょう。
0412１３２人目の素数さん
2007/09/16(日) 19:53:40バージョン5の定義ありがとうございます。
自分で計算してないのですが>>387-388を見るとやっぱりF_(ε_0)(x)に到達して
そうな感じですねぇ・・・。
ヴァージョン６楽しみにしています（笑）
>>405
なるほど。おそらくその定義がn重帰納関数の最低ラインっぽいですね。
前に言われていた所謂「正規形」ってやつかもしれません。
0413１３２人目の素数さん
2007/09/16(日) 21:02:03ﾊｧ?
■ このスレッドは過去ログ倉庫に格納されています