巨大数探索スレッド8

これを普通の言葉で表すと、

n=m=0 の時、
Ack_new(n,m,step) = step+2

n=0, m≠0 の時、
Ack_new(n,m,step) = Ack_new(0,m-1,step+1)+1

n≠0, m=0 の時、
Ack_new(n,m,step) = Ack_new(n-1,1,step+1)

n≠0, m≠0 の時、
Ack_new(n,m,step = Ack_new(n-1,Ack_new(n,m-1,Ack_new(n,Ack_new(n,m-1,step+1)-1,step+1)+1),Ack_new(n,Ack_new(n,m-1,step+1)-1,step+1))

>>902-904
なんかおかしくなったので無かったことに。

>>902-904
間違ったので書きなおします。

// step=s の時にAck(n,m)を呼んだ後のstepの値
int Ack_s(int n, int m, int s){
　　if(　n==0　&&　m==0　)　return s+1;
　　if(　n==0　)　return Ack_s(0,m-1,s+1);
　　if(　m==0　)　return Ack_s(n-1,1,s+1);
　　return Ack_s(n-1,Ack(n,m-1,s+1),Ack_s(n,m-1,s+1));
}

// step=s の時のAck(n,m)の値
int Ack(int n, int m, int s){
　　if(　n==0　&&　m==0　)　return 1;
　　if(　n==0　)　return Ack(0,m-1,s+1)+1;
　　if(　m==0　)　return Ack(n-1,1,s+1);
　　return Ack(n-1,Ack(n,m-1,s+1),Ack_s(n,m-1,s+1));
}

int Ack_n(int n, int m, int s){
　　if(　n==0　&&　m==0　)　return s+1;
　　if(　n==0　)　return Ack_n(0,m-1,s+1)+1;
　　if(　m==0　)　return Ack_n(n-1,1,s+1);
　　return Ack_n(n-1,Ack_n(n,m-1,s+1),Ack_n(n,m-1,s+1));
}

これは明らかに >>906 の Ack, Ack_s 以上の値。

p=max(m-1, s+1)として
int Ack_n2(int n, int p)
を考えると、本質的にアッカーマンと変わらないことが分かる。
つまり、>>898 のAck によるstepの増加度はAckの増加度と同程度である。

>>900
ああ、そうだねC言語を持ち出した俺がわるかったｗ

それでは環境依存や最適化は行わないようにC言語には
厳密に適用されていないルールをここで適用する

ルール１：コンパイル時の最適化は、一切行わない
ルール２：プリプロセッサは一切適用しない
ルール３：外部ライブラリは一切使わない
ルール４：関数の評価順序は次の通りに固定する
　・必ず引数の左から右に評価する（カンマ演算子とルールは一緒）
　・引数が関数の場合、かならず引数として適用された関数の評価が全て完了するまでネストした外の関数に値を渡さない
　・関数内や演算で共通変数を用いる場合評価時点での値を必ず用いる
ルール５：値を見積もるために勝手に手続きを変えない
　・プログラムによる提示は実行時評価が目的なので評価結果が変化するような加工は認めない

>>901のような指摘は、自分がルールを示さなかったこともあり、指摘内容ももっともであり、自分が目的とする意図と同じであるので
上記、ルール４にて、評価順序を明確にした

したがって、Hackは、たとえ同じ引数であっても、評価するタイミングで毎回違う値を返すことが目的なので
評価しにくいからと言って意図しないような値を返す変形はみとめない

int s_1 = 0;
int Step_1(int x){
　　s_1++;
　　return x+1;
}

int s_2 = 0;
int Step_2(int x){
　　s_2++;
　　if(　x==0　)　return 1;
　　else　return Step_2(x)+1;
}

int s_3 = 0;
int Step_3(int x){
　　s_3++;
　　Step_3(0);
　　return x+1;
}

上記のようにStep_1とStep_2とStep_3は、関数の結果として、同じx+1の値を返すわけだがs_1とs_2とs_3の値が異なることは明確である
この繰り返しによるstep数の増大が目的なので同じ値を返すからと言って勝手にStep_1をStep_2をStep_3を入れ替えるような操作はしないで貰いたい

>>907
定義したAckとAckのstep数の大きさの比較を指摘しているけど、そんなことはだれも目的にしていないよｗ

動的に変化するstep数を使って関数が最終的に返す値を動的に増大させることが目的
できれば関数の最終出力結果に対して議論して欲しいんだけどｗ

HaskellでOK

>>910
私が書いたことを全く理解してないのか。

>>898 の Ack の戻り値は、コール時のstepの値に依存するので、
Ack の戻り値には影の引数stepが関係してる。
また、Ackをコールしたあとではstepの値が変化している。

>>906 の Ack は影の引数stepを直接の引数に変えたもの。
>>906 の Ack_s は >>898 のAckのコール後のstepの値を返すもの。

>>898 の Ack の戻り値と >>906 の Ack の戻り値は完全に一致するんですよ。
プログラム開始時のstepの値はゼロなので、
>>906 に、int main(){return Hack(9,9,0);} を加えれば、
main の戻る値は >>898 と同じになります。

↑最後の３行は嘘

>>906 の Ack, Ack_s のペアよりも、
>>907 の方が大きな値を返し、記述も非常に簡単。
しかも、数学的な記述に簡単に直せる。

だから、>>898 の大きさを見積もるには >>907 の大きさを見積もれば良いんです。

Hack も同じようにもっと簡単な形に変形してから大きさを見積もる。

で、結論である >>898 の大きさは、
F[ω*2](9) 程度。

>>908
戻り値が環境依存な値になったのは記述の方法が悪かったから。
正しく書けば環境依存にはならない。
変なルールを追加する必要もない。

で、C++言語による記述の例が >>764 にある。

たとえば、F[ω^2](9) であれば、
int a(int b,int c,int d){return b+c&&d?a(b-!c,c?c-1:d,a(b,c,d-1)):d+9;}int main(){return a(9,9,9);}
とC++の機能を使わなくても同じ99文字で記述できる。

これより文字数が少ないか、これより大きな値を返すか、別の数学的意味があるか、
じゃないと。

>>909
>>906 は Ack の戻り値だけじゃなく、
Ack コール時のstep の増加量もちゃんと Ack_s で記述してるのですよ。
step の増加量が記述出来ないと、
Hackの大きさも記述出来ない訳なので。

長くなるので Hack の直接引数による記述をするのは避けてましたが、
理解されていないようなので、書きます。

>>906 に以下を加えると、main の戻り値は >>898 と同じに。

int Hack(int n, int m, int s){
　　s　=　Ack_s(n,m,s) + Ack(s,s,s);
　　if(　n==0　&&　m==0　)　return s;
　　if(　n==0　) return n = Hack(0,m-1,s), s = Hack_s(0,m-1,s), m = Hack(0,m-1,s), Ack(n,m,s);
　　if(　m==0　)　return Hack(n-1,s,s);
　　return m=Hack(n,m-1,s), s=Hack_s(n,m-1,s), Hack(n-1,m);
}
int Hack_s(int n, int m, int s){
　　s　=　Ack_s(n,m,s) + Ack(s,s,s);
　　if(　n==0　&&　m==0　)　return s;
　　if(　n==0　) return n = Hack(0,m-1,s), s = Hack_s(0,m-1,s), m = Hack(0,m-1,s), Ack_s(n,m,s);
　　if(　m==0　)　return Hack_s(n-1,s,s);
　　return m=Hack(n,m-1,s), s=Hack_s(n,m-1,s), Hack_s(n-1,m);
}
int main(void){
　　return Hack(9,9,0);
}

こうすればmainの戻り値は >>898 より大きくなり、見積もるのも簡単に。

int Ack_n(int n, int m, int s){
　　if(　n==0　&&　m==0　)　return s+1;
　　if(　n==0　)　return Ack_n(0,m-1,s+1)+1;
　　if(　m==0　)　return Ack_n(n-1,1,s+1);
　　return Ack_n(n-1,Ack_n(n,m-1,s+1),Ack_n(n,m-1,s+1));
}
int Hack_n(int n, int m, int s){
　　s　=　Ack_n(n,m,s) + Ack_n(s,s,s);
　　if(　n==0　&&　m==0　)　return s;
　　if(　n==0　) return n = Hack_n(0,m-1,s), s = Hack_n(0,m-1,s), m = Hack_n(0,m-1,s), Ack_n(n,m,s);
　　if(　m==0　)　return Hack_n(n-1,s,s);
　　return m=Hack_n(n,m-1,s), s=Hack_n(n,m-1,s),Hack_n(n-1,m);
}
int main(void){
　　return Hack_n(9,9,0);
}

贅肉をそげば単なる2変数アッカーマンを2段階にしただけであることが分かる。

hoge

もうネタ切れ？

もう素人に手が出せるような話じゃなくなったからな

巨大数スレッドの１（８年前　日韓Ｗ杯の年）

■■■史上最大の数　グラハム数■■■

1 名前：１３２人目の素数さん ：02/02/18 20:06
の大きさってどれぐらいなの？
ギネスブックに出ていたんだが、証明に使われた最大の数という
ことだが‥‥‥‥？

の>>1です　お久しぶりです　ってもう誰もいないのかな
もやしっ子さんとかふぃっしゅ氏とか‥‥‥

もやしっ子さんやふぃっしゅ氏の理解の範囲を超えてしまったからね。

で、いま誰が一番巨大数を理解してるんだ？
というか、いま一番でかい巨大数はどれなの？

>>921

まじですか。
あれから３〜４年くらいが一番盛り上がった時期でしょうか。（遠い目）
mixiのコミュの動きもないようですね・・・

>>923
計算可能な範囲ではハーディー関数の中に大きな帰納的定義の順序数を入れたものが大きい。
このスレでアルゴリズムを具体的に示しているものの中では
HardyFunctionと添え字付きψを用いた >>6 や >>696
もっと大きな帰納的順序数とその構成もいろいろと出ている。

計算可能な範囲に限定しなければ
ハーディー関数の中に大きな可算順序数をいれたものや、
チューリング次数0^(大きな可算順序数)のオラクルを持つマシンによるビジービーバー関数
など。
大きな可算順序数とその構成の定義もいくつか出ている。

いずれの場合も、
大きな数を定義するには大きな順序数（とその収束列）を定義する必要がある。
その為には大きな基数の知識も必要になる。

順序数やハーディ関数は高校で習えますか？

8年も続いてるのな
ログみて面白そうだったのできますたage

>>926
習わないと思われ

>>923
このスレの中で帰納的定義の順序数を一番理解しているのは >>6 だろうな。
（もういないんじゃないか？）
一番幅広く理解しているのは俺だと思う。

順序数やハーディ関数は大学で習えますか？

早く勉強したいなら教えてくれるまで待ってないで自分で勉強しろ
と思うけど、中学生や高校生が理解できる教材もないだろうから

どうしてもというなら俺が直接教えてやっても良い。
ただし高校生までで東京に来られる人限定。
（大学生以上なら自分で勉強しろ）
授業料はいらないが俺の電車賃と場所代くらいは払ってくれ。

マジかよ

それもいいけど、日本語で読める教科書とかないんですかね。
ハーディー関数とか直接記述してなくてもいいから、それに繋がる
ような話題を扱ってるような本で、おすすめのがあったら教えてほしい。

>>930
このスレでやってる数学はマニアックなので、いくら待っても授業で習うことはないだろう。
学びたいなら自分で学ぶしかない。

このスレの過去ログをきちんと読んだりネットで調べたりするだけでも、
ここに書かれていることはある程度理解できるようになるんじゃないかな。
自分でしばらく考えても分からないことがあれば、ここで質問すれば誰かが答えてくれると思う。

ふぃっしゅ数を超えようってのはされてないの？
新しいのを作って

今北
こんなん専門知識なきゃ手が出ないだろ…

俺にはふぃっしゅ数の仕組みすらよく分からん
アッカーマン関数使ってどうしてんの？

>>935
ふぃっしゅ数＋１

>>937
それ見飽きた
ふぃっしゅ数やグラハムのようなの使わずに一からってこと

結局は関数の増大率の問題だからなぁ

これは初心者は最初何を勉強すればいいの？

あげちゃえ

●小学生
大きな数を黒板やノートに書いていく競争になった場合、
99999..... や 100000.... と書いていく場合が多いと思うが、
当然111111.... と書いていく方が書くのが早く、場所も取らない為有利である。

●中学生
指数表記を習ったら
     .
    .
   7
  7
 7
7
と書いていく。
2〜9までの中で7が一番書くのが早い為である。
もちろん、7の左側は書かずに1画で書くこと。
1に見える文字が混じらないように。
7の左側を書かない書き方に抵抗があれば6にする。
ただし0に見える文字が混じらないように。
相手より早くかける自信があったり時間制限が無ければ素直に9と書いても良い。
 1111.....
9
よりも大きいと相手を説得できるだけの知識は最低限身につける。
（右上から計算することと、1111.... より 7^7^7... の方が大きいと言えれば良い）

階乗を習っても、9!!!... と書くよりは上の7での指数表記の方が普通は書くのが早い。
場所に制限があり、かつ相手に多重階乗だと指摘される心配がない場合のみ
9!!!!!.... と書いていく。

11^11^11…
の方が早くね？

>>940
とりあえず過去ログに一通り目を通してみるといい。
全ての書き込みが正しいとも限らないので、
重要でなさそうなことは読み飛ばしつつ。

>>943
そうか？
おれは11より1画の7の方がずっと早く書けるけど。

>>940
>>580
コンウェイのチェーン表記は飛ばしても良いし、
ハーディー関数の前にふぃっしゅ数V5を入れてもいい。
ビジービーバー関数はもっとずっと前でもいい。
（他に必須なやつ、なんかあった？）

その先は好きな順で

欧米人の7の書き方は時間がかかる

>>942
小中学生の巨大数記述競争は結構面白そうだな
みんな掛け算や階乗、数字の羅列をしまくる中で思いがけない方法を考える人がいそうで

階乗とか知らなくて、適当に矢印書いて遊んでたらチェーンだったでござる

説明出来なくて良いなら
それっぽい適当な記号を書いておけば良いんじゃね？
相手がどんな数を書いても、「こっちの方が大きいよ」と言えばいい。

うちの小学校1年の娘には
グラハム数とマーロ基数の名前だけは教えてある。

>>949
娘ひとり勝ちktkr
でも小学生とかだと認知度とかそんなの考えずに狭い範囲での勝ち負けに終始しそうだな
例えば黒板を左右に分けて勝負する場合右のやつが「左の数字＋1」とかやりそうだし

age

228

保守