巨大数探索スレッド7
■ このスレッドは過去ログ倉庫に格納されています
0001１３２人目の素数さん
2006/11/19(日) 23:44:01http://www.geocities.co.jp/Technopolis/9946/
前スレ、過去スレ、避難所はこのページからどうぞ。
「前の数＋1」
「1/x x→0」
「∞」
「９を延々と書き続けるプログラム」
「本日からこのスレでは、いっさいの数学的ではない話を禁止する。
私以外で検証する能力を持っている人間はいないようなので、
数学的に明確に証明できた場合以外は反論しないように。
特に今日のような低俗な煽りには徹底して放置で対応すること。」
という類の投稿は放置推奨。
0232通りすがり
2007/04/09(月) 20:13:01http://2ch-library.com/uploader/src/2ch6734.txt
>>230 は検証せずにイメージで書いちゃったけど、
> M[1](n) は 前スレ >>863 の mm(n) を大きく超える。
これは嘘でした。
0233１３２人目の素数さん
2007/04/09(月) 22:59:54サンクス。念のため、魚拓で保存しておきました。
http://symy.jp/?eblK
0234１３２人目の素数さん
2007/04/16(月) 10:16:050235１３２人目の素数さん
2007/04/16(月) 19:04:010236１３２人目の素数さん
2007/04/16(月) 20:12:350237１３２人目の素数さん
2007/04/16(月) 21:43:33たいてい計算不可能なんじゃないかな
0238１３２人目の素数さん
2007/04/16(月) 21:44:320239１３２人目の素数さん
2007/04/17(火) 17:11:540240１３２人目の素数さん
2007/04/23(月) 22:12:22興味があるので、このスレは10文字で云々って頃から見てました
プロジェクトX風ナレーションで、マジ泣きしたこともありました
で、ふと思ったんですが、現在20文字部門最強の
＞f(n):=nに階乗をn回
＞f^9!(9)
と、
グラハム数をグラハム数!回階乗
では、どちらが大きいんでしょうか？
表記のルールに反するので対象外だとは思いますが、私の知識だと「f(n)」
ってのが既に何なのか判らないので、比較ができません
どなたか教えて頂けませんでしょうか？
また、「グラハム数」の表記が認められた場合、どのような表記が最大になる
のでしょうか？
0241１３２人目の素数さん
2007/04/24(火) 05:02:59グラハム数！回階乗なんかしなくても。
0242１３２人目の素数さん
2007/04/25(水) 07:32:47ありがとうございます
意外と小さいんですね
って、それだけグラハム数が大きいってことで、そんなのもミクロの世界に追いやる
ふぃっしゅ数が偉大だってことなんでしょうけど
0243１３２人目の素数さん
2007/04/25(水) 16:53:39あ、でも数を擬人化すればこそこんなバトル風になったのか。
0244１３２人目の素数さん
2007/04/25(水) 19:23:30こうですか？ わかりません＞＜
0245１３２人目の素数さん
2007/04/25(水) 19:52:37です
基本的な数学の概念自体判ってないので、自分なりに理解する為に
脳内で物語とかを展開しながらROMってます
何スレか前、RPG風にスレの流れを書きましたが、あんな感じです
ふぃっしゅ数は打たれても打たれても立ち上がってくる、ジャンプ系の
主人公って感じでしょうかね
戦隊組んだら、ふぃっしゅ数は間違いなく赤だと思います
0246１３２人目の素数さん
2007/04/25(水) 22:18:170247１３２人目の素数さん
2007/04/26(木) 07:57:00探索は限りないんだろうか。なんかの構造的なシフトでもどっかにあるんだろうか。
0248１３２人目の素数さん
2007/04/27(金) 21:00:380249１３２人目の素数さん
2007/04/27(金) 21:36:18か
9999→9999→9999→99999
か
999→999→999→999→9999
か
99→99→99→99→99→99→99
か
9→9→9→9→9→9→9→9→9→99
のどれかじゃないかと思うんですけど、>>240なので比較できません(;´Д`)
0250１３２人目の素数さん
2007/04/27(金) 21:43:260251１３２人目の素数さん
2007/04/27(金) 22:51:41一番上以外は全部グラハム数より遥かにデカイ
当然のごとく一番下が最大だろう
0252１３２人目の素数さん
2007/04/29(日) 02:00:13文字の規定はどうするんだ？
ある記号に意味をいくらこめても良いんじゃ意味ないし。
0253１３２人目の素数さん
2007/04/29(日) 06:35:28ならないんですね
数字2つなら「a→b=a^b」でいいけど、3つ以上になると定義の説明だけで
20文字超えそう
0254１３２人目の素数さん
2007/05/02(水) 22:33:260255１３２人目の素数さん
2007/05/02(水) 22:58:18９↑↑↑(９！) ＜ 「２０文字最強」 ＜ ９↑↑↑(９！＋２) ＜ ２↑↑↑↑３ ＝ ２→３→４
0256１３２人目の素数さん
2007/05/02(水) 23:59:59証明付けてやったろうかと思ったら思いのほかめんどかったし、
その間に別のレスがついたし。
まぁこの程度の比較してるだけなら証明なんて不要なんだろうと思ったし。
0257１３２人目の素数さん
2007/05/03(木) 07:38:1120文字部門は f^9! と括弧なし
30文字部門は f^(99!) と括弧あり
な理由がわからん。
0258１３２人目の素数さん
2007/05/03(木) 20:08:430259１３２人目の素数さん
2007/05/04(金) 23:20:50理解してるだろう・・・。
0260１３２人目の素数さん
2007/05/10(木) 22:10:08ただ単にn文字で大きな数では曖昧なため、
C++言語を使ったルールを考えてみました。
C++言語のnトークン(n語)で大きな数をつくるというものです。
int main();
がどれだけ大きな整数を返すか競います。
----------ルール-----------
int 型は無限長符号付整数とします。
数値（即値）は十進表記のみであらわしますが、
数値だけは例外として桁数をトークン数に数えます。
（コメントや空白はカウントしません）
以下のような、処理系に依存するコードはNGとします。
引数の評価順に依存するコード、
不定値参照、
sizeof 演算子、
ポインター <=> 0以外の整数値 のキャスト
など
プリプロセッサの使用、ライブラリの使用は不可
0261１３２人目の素数さん
2007/05/10(木) 22:12:08int main(){
return 99;
}
// 20 word
int main(){
return 9<<(9<<(9<<99));
}
// 30 word
int main(){
int a = 99, b = a<<a;
while (b--)
a <<= a;
return a;
}
// 40 word
int main(){
int a = 9<<9, b, c = a;
while (b = a, c--)
while (b--)
a <<= a;
return a;
}
0262１３２人目の素数さん
2007/05/10(木) 22:12:53int func(int a, int b){
return
a ?
b ? func( a-1, func(a, --b) )
: a
: ++b;
}
int main(){
return func(9,9);
}
0263１３２人目の素数さん
2007/05/10(木) 22:17:02// 定義域: a >= 0, b >= 0
// サイズ: 42
int Ackermann(int a, int b){
return
a ?
b ? Ackermann( a-1, Ackermann(a, --b) )
: Ackermann(--a, 1)
: ++b;
}
// 返す値: クヌースの矢印表記 a ^^...^^ b (^ がc個)
// 定義域: a >= 1, b >= 0, c >= 0
// サイズ: 44
int Knuth(int a, int b, int c){
return
c ?
b ? Knuth( a, Knuth(a, --b, c), c-1 )
: 1
: a * b;
}
0264１３２人目の素数さん
2007/05/10(木) 22:17:35// 定義域: s >= 1, p[i] >= 1
int Conway(int s, int *p){
int i = s, int *q = new int[s];
while (i--)
q[i] = p[i];
if (s == 1)
return p[0];
if (p[s-1] == 1)
return Conway(s-1, p);
if (s == 2){
q[1] --;
return b[0] * Conway(s, q);
}
if (p[s-2] == 1)
return Conway(s-2, p);
q[s-2] --;
q[s-2] = Conway(s, q);
q[s-1] --;
return Conway(s, q);
}
0265１３２人目の素数さん
2007/05/11(金) 22:48:13http://2ch-library.com/uploader/src/2ch6803.cpp
0266１３２人目の素数さん
2007/05/16(水) 20:59:14>>205 に定義されているΨ(ψの極限)を使って、
hardy[ψ(0, Ψ)](99) を返す関数を作ってみました。
http://2ch-library.com/uploader/src/2ch6886.cpp
0267１３２人目の素数さん
2007/05/16(水) 21:08:19n文字（またはn単語、nトークンなど） で表せる最大の可算順序数を
o(n) とした場合、この極限 lim o は可算なのだろうか？
可算だとすると、
帰納的定義では到達できないほど大きな可算順序数が存在することになる。
非可算（つまりΩ）になるとすると、
可算順序数の列で、極限が非加算になるものが存在することになる。
0268１３２人目の素数さん
2007/05/16(水) 21:28:350269１３２人目の素数さん
2007/05/16(水) 22:08:40> 可算順序数の可算列ではω_1にはならないんじゃないか？
ということは、
帰納的定義では到達できない最小の順序数を☆_0とし、
☆_0と帰納的定義では到達できない最小の順序数を☆_1とし、
....
☆_n の極限を☆_ω とし、
....
☆_☆_...._☆_☆_0 を ★_0 とし、
....
とか定義できるのかな？
0270１３２人目の素数さん
2007/05/17(木) 09:11:32基本的な概念だから、順序数を使って急増加函数を作りたいなら
勉強したほうが良いよ。無理にとは言わないけどね。
n文字を用いて或る数を表す、とかいうときの文字数は
Peano算術なりZFCなりの論理式の文字数と考えれば良いだろう。
μxP(x)と表したときのPでも良いだろうし。
Pに量化記号が無制限に入っていいことにすると、
急増化函数の存在がZFCから独立、
なんてことが起こるから基礎論に詳しくないとどう考えていいか分からなくなるけど。
0271１３２人目の素数さん
2007/05/17(木) 23:48:47わざわざどうも。
私は基礎論も順序数論も集合論も詳しくないので、先は長そう。
帰納的定義によりたどり着ける順序数は、
言語によらず同じで、
☆_0 も１個に定まると楽観的には思いますが、
いかがでしょうか。
H[☆_0](n) は計算不可能（アルゴリズム存在せず）なので、
結局BB(n)と実質同じになります。
●このスレで出た最大
順序数、基数、濃度: Ψ
可算順序数: ★_0
帰納的定義の可算順序数: ψ(Ψ)
関数: >>230
帰納的定義の関数: H[ψ(Ψ)](n)
0272１３２人目の素数さん
2007/05/18(金) 19:13:44保存しておきました。
http://symy.jp/?C1vg
0273１３２人目の素数さん
2007/05/19(土) 14:14:250274１３２人目の素数さん
2007/05/19(土) 23:56:47もう既に名前がついてるんですか。
>>202では、
ψ_α(0) を、濃度がω_αである最小の順序数としていますが、
ψ_α(0) = ☆_α としてもまったく同じように各順序数の収束列を定義でき、
>>203 や >>266 のプログラムもまったくかわらず、
H[ψ(Ψ)](n) の値もまったく同一になりますね。
（この場合、Ψ=★_0）
さらにψ_α(0)を小さく定義することもできそうです。
（つまり帰納的定義の範囲内）
こう考えると、
はじめは H[ψ(Ψ)](n) の定義には巨大な基数が現れるので、
H[Γ_0](n) に比べて革命的に大きくなっているように見えたんですが、
だんだんと普通の拡張に見えてきました。
プログラムも２倍程度に増えただけですし。
0275１３２人目の素数さん
2007/06/17(日) 15:05:450276１３２人目の素数さん
2007/06/19(火) 23:08:35任意の自然数cに対しある数nが存在しn<xならばf^c(x)<g(x)が成り立つならばgはfより本質的に大きい。
というアイディアはどうでしょうか。既出かもしれませんが。
0277１３２人目の素数さん
2007/06/22(金) 12:35:51g = f^x(x) と定義すれば、gはfよりも本質的に大きくなるね。
通常の関数であれば十分に本質的に大きい、と言えるだろうけど、
たとえば>>230のような関数に対してこのような拡張をしたところで、
本質的に大きいとは言えないかも。
0278１３２人目の素数さん
2007/06/25(月) 22:27:46ここにある「C」は、「An Ordinal Notation」の段階で
>>202 の添字つきψと同じ順序数まで表せる模様。
さらに、
「A Stronger Ordinal Notation」
「Second Order Arithmetic」
「Beyond Second Order Arithmetic」
と続くので、相当巨大な順序数が作れそう。
0279276
2007/06/26(火) 22:59:19２７６ですが、どうもこの方法は原始帰納関数？では上手く機能すると思うのですが、
それ以上となると駄目なような気がなんとなくしてきました。
0280１３２人目の素数さん
2007/06/26(火) 23:49:45計算可能な関数に関しては、
Hardy Function を用いて、F[順序数](n) という形に近似して順序数の大小で比較。
Hardy Function を本質的に超える関数が出てくるまでは、
これで大小比較が可能。
（順序数が本質的に大きいかどうかという問題になる）
---例---
Knuthの上矢印 3(↑^n)3 ≒ F[ω](n)
n個のnからなるConwayのチェーン ≒ F[ω^2](n)
↑n (3,3,3) ≒ F[ω^3](n)
Ak(n, 3) = ≒ F[ω](n)
Ak を多変数に拡張、Ak(n個のn) ≒ F[ω^ω](n)
Ak を２重リストに拡張、Ak([n個のn], [n]) ≒ F[ω^ω^ω](n)
Ak を多重リストに拡張、Ak(n重リスト) ≒ F[ε_0](n)
ちなみに、g = f^x(x) とするのは、F[順序数](n) の順序数に1を加えるのと同じ効果。
----
計算不可能なものも含めた場合には、
ある程度小さなものは、
>>230 の形に近似して順序数の大小で比較すれば良いが、
順序数をマシンで生成させ、これを引数とするHALT[順序数] 命令にすると、
M[順序数](n) よりも大きくなるため、順序数での比較は不可になる。
0281たろう
2007/06/27(水) 23:00:18http://up.spawn.jp/file/up29497.txt.html
F[ω^3] までゆっくりで、一気に F[φ_ω(0)] まで飛んでます。
F[ω^4], F[ω^ω], F[ε_0] なども作ってみたけど、
F[φ_ω(0)] より大きくなってしまいました。
順序数を使う２個は >>278 の C を参考にしてます。
「An Ordinal Notation」より手前の段階のを多変数にしてます。
veblen関数を普通に多変数にしたものよりは効率がよさそうです。
（+ の定義まで含まれているのと、収束がちょっと簡単）
いずれは
「An Ordinal Notation」や「Beyond Second Order Arithmetic」、
「An Ordinal Notation」から「Beyond Second Order Arithmetic」を順序数回繰り返したもの
など、より大きなものを作る予定。
あと、>>280 にある、
アッカーマンの拡張で F[ε_0] やその先まで到達する方法をまとめました。
http://up.spawn.jp/file/up29500.txt.html
0282たろう
2007/06/30(土) 05:40:21M[順序数](n) の関数を作るには、
>>233 の基本命令に
test ** という命令を加えればよい。
これは、ラベル ** へジャンプした場合に halt で停止する場合はポインタ位置を1にセット、
無限ループする場合はポインタ位置に0をセットする命令。
この命令は引数として順序数を取る。
ジャンプ先に、引数以上の test ** 命令が出現する場合には停止問題は解決できない為、
ジャンプ先で、halt より前に、引数以上の test ** 命令が出現する場合は halt と同じ動作をする。
引数の順序数の与え方は、
たとえばM[ω](n)を定義するマシンの場合には、
ポインタ位置から１が続く個数を数え、これを引数nとする。
M[C(a, b, c) の極限](n) を定義するマシンの場合は、 ...(Cは>>278のもの)
順序数を 0 , C ( ) の５個の文字で表し、
0 には 1 を、
, には 11 を、
C( には 111 を、
) には 1111 を、
割り振り、
文字の境目を 0 としてエンコードしたものを引数とすればよい。
たとえば、ポインタ位置から 111 0 1 0 11 0 1 0 11 0 1 0 1111 となっている場合は
引数は C(0,0,0) と解釈する。
※ C(a, b, c) は0とCのみでCの極限未満のすべての順序数を表現可能
0283１３２人目の素数さん
2007/06/30(土) 05:55:11>>233 のようなマシンでは定義が非常に複雑になるが、
C++ のような高級言語なら出来そうである。
>>266 のように、ordinalを、0 から始めて再帰的に、
１個前の順序数を使って定義する
収束列を使って定義する
としていけばすべての帰納的順序数を表現できる。
これを引数にとるような test ** 命令を持つマシンでの
n命令での最大のステップ数が M[帰納的でない最小の順序数](n) である。
（>>269 でいう ☆_0）
さらに、☆_a をあらかじめ定義しておくことで、
M[★_0](n), M[☆_2](n) なども定義できる。
ただ、このようなルールはマシンを定義する段階で必要であるので、
すべての順序数を定義できるわけでなく、
いままで人間が到達出来ていない最小の順序数
のようなものに対してマシンを定義できない。
たとえば、M[Ω](n) なんかは、可算順序数がすべて表現可能な
方法が見つかってから始めて定義できる。...つまり定義できない。
0284１３２人目の素数さん
2007/06/30(土) 06:07:41>>280 の後半「順序数の比較は不可になる」というのは嘘で、
M[順序数](n) として大小比較が出来そう。
----
☆_0 の収束列を、
C++ n語で表現できる最大の帰納的順序数
とすれば、
F[☆_0](n) が定義できる。
「C++ n語で表現できる最大の帰納的順序数」を求めるアルゴリズムは存在しないため、
これは BB と同程度の大きさとなる。
F[帰納的順序数](n) はすべて計算可能であり、
すべての計算可能な関数は、F[ある帰納的順序数](n) で押さえられる。
M[0](n) ≒ F[☆_0](n) であり、
M[1](n) ≒ F[☆_1](n) であり、
おそらく、M[a](n) ≒ F[☆_a](n) といえる。
0285もやしっ子
2007/07/05(木) 03:42:16さっぱりです。
何とかします。
0286１３２人目の素数さん
2007/07/06(金) 18:18:38ここに載ってるのとふぃっしゅ数だったらどっちがでかいのか？
表記法の説明（英語）
http://www.polytope.net/hedrondude/array.htm
0287たろう
2007/07/06(金) 21:49:47http://www.geocities.co.jp/Technopolis/9946/log/ln023.html
S変換がハーディー関数の順序数にωを足す位の変換。
つまり、F[a](n)にS変換を行うとF[a+ω](n)になる位。
SS変換はω^2を足すのと同等、
SSS変換はω^3を足すのと同等、
....
S^i変換はω^iを足すのと同等、
--------
(S^n変換)f(n) ≒ F[a+ω^ω](n)
最初の関数にアッカーマンを使っているが、
f(x) = x+1 としても大差なし。どちらもF[ω^ω](n)程度となる。
>>281の多変数＃と同程度。
0288たろう
2007/07/06(金) 21:53:01Extended Operators の下の方の4変数の段階で F[ω^2](n) 程度。
0289たろう
2007/07/06(金) 22:14:29こちらの >>10 にバージョン５の記述がありましたね。
m(2) がハーディー関数の順序数に1を加えるのと同等、
m(3)m(2) がハーディー関数の順序数にωを加えるのと同等、
m(4)m(3)m(2) がハーディー関数の順序数にω^2を加えるのと同等、
....
f5(n) ≒ F[ω^ω](n)
となり、古いバージョンとほぼ同じとなるようです。
0290１３２人目の素数さん
2007/07/06(金) 22:19:59いよいよこのスレの終焉も近い？
0292たろう
2007/07/06(金) 22:49:37m(2) がハーディー関数の順序数に1を加えるのと同等、
m(3)m(2) がハーディー関数の順序数にωを加えるのと同等、
m(4)m(3)m(2) がハーディー関数の順序数にω^ωを加えるのと同等、
m(5)m(4)m(3)m(2) がハーディー関数の順序数にω^ω^ωを加えるのと同等、
....
f5(n) ≒ F[ε_0](n)
0293１３２人目の素数さん
2007/07/07(土) 21:41:330294１３２人目の素数さん
2007/07/10(火) 09:20:520295１３２人目の素数さん
2007/07/31(火) 13:41:180296１３２人目の素数さん
2007/08/02(木) 02:56:33無限大を超えることになる。
無限大×∞
∞＾∞
∞＾∞＾∞ とかぎりなく増やせるということは、
さらに、上数があるということだろうか？
0297感覚的限界
2007/08/02(木) 16:38:09∞ = 1+1+1+…
として
2∞ = (1+1+1+…)+(1+1+1+…)
= 1+1+1+1+1+1+…
としてしまうと∞と変わらなくね？となるので
「1が無限個ある」はまだいいけど「1が2∞個ある」は禁止。
きちんと掛け算を定義しないといけなくてそれをやってるのが順序数。
で
「∞に＾∞を無限個つなげる」から先はどうすればいいんでしょうね。
0298１３２人目の素数さん
2007/08/02(木) 17:37:180299１３２人目の素数さん
2007/08/03(金) 23:40:15∞ ==> ω
0300１３２人目の素数さん
2007/08/04(土) 17:29:010301１３２人目の素数さん
2007/08/05(日) 00:41:21ω+1とか定義できるしなあ。
>>297の言いたいこととはちょっと噛み合ってないんじゃないかと思われ
0302１３２人目の素数さん
2007/08/09(木) 15:55:06フォームです、(直線的)のアレイ記法や、広げられて(次元)のアレイ記法や、いくつかの
変更があるtetrationalアレイ記法などのように。 元々、様々なアレイ記法には、いくつ
かの規則がありました--直線的のための5、広げる、私がtetrationalであっ、それでも、
今それを解決しようとして、3つの規則しかなくて、すべてのアレイの世話をするtetrati
onalアレイのずっとも先の7。
--------------------------------------------------------------------------------
どのように、それ、Started
数年間、私は数多く興味を持っています、数個のために名前を鋳造しさえするまで私の
「「不-ライオン」番号」ページを参照してください。 ある日(およそ20年前)、私は強国を
超えたオペレータ、tetrationなどのオペレータ、pentation、hexationなどについて議論し
たものを本(名前を覚えていない)に読み込みます。 これによって、私は次元スペース(私が
現在呼ぶ空間、最高の次元の、そして、trimensionalなquadramentionalなど)を超えた極端
な空間と同様により極端な数を調査したくなりました。 時間が経ったように、私はその本の
見られるオペレータにextentionを開発し始めました、私が拡張オペレータに言及するつもり
であるこれら。 その後、AckermannのFunctionやコンウェイのChained Arrow Notationなど
の知られている大きい数の機能を調べた後に、私はこれらのよく知られている機能と拡張オ
ペレータを比べることができました。 オペレータのはるかに凌がれたAckermannのFunctionを
広げて、実際にコンウェイのChained Arrowと比較することができました--詳細がないかどうか
M.ロブの大きい数のページでチェックしてください。 その後、私は拡張オペレータを広げる
タスクを引き受けました--私は、後で4つの番号、および次のextentionが5時までに拡張オペ
レータを定義することができると発見しました。 これは私のArray Notationの開発の始まり
です。
0303１３２人目の素数さん
2007/08/09(木) 19:59:480304１３２人目の素数さん
2007/08/11(土) 22:17:300305１３２人目の素数さん
2007/08/12(日) 00:40:16>>302
You might wanna post it in English.
0306１３２人目の素数さん
2007/08/23(木) 20:28:14足し算a+bは1を足すのをb回繰り返す
掛け算a*bはaを足すのをb回繰り返す
階乗a^bはaかけるのをb回繰り返す
タワーa↑↑bはaをb乗するのをb回繰り返す
タワーa↑↑↑bはa↑↑bをb回繰り返す
タワーa↑^nbはa↑(n-1個)bをb回繰り返す
これを改良したのがコンウェイのチェーン表記
アッカーマン関数
原始帰納的でない帰納的関数
ack(0,n)=n+1
ack(1,n)=n+2
ack(2,n)=2*n+3
ack(k,n)はack(k-1,n)と階乗を使って表わせる。
以下、俺の理解
バード数
タワーと、グラハム数を使った関数を用いた数。
ふぃっしゅ数
バージョン1のS変換は↑^nのこと
その次のS変換(SS変換?)は↑の代わりにアッカーマン関数を使ったもの
それらの変換を使って定義した数
ビジービーバー関数
どんな計算可能な関数よりも増加率の大きい関数。
「じゃあ、俺今まで出た一番でかい関数+1ね。」っていうズルと一緒
ハーディ関数：ω(無限順序数のうち最小のもの)が計算可能でないのでズルに思える。
多分、S変換とバード数の回転だと、初期の値の振る舞いはバード数が勝つ(グラハム数を使っているため)が
基本的にタワーよりはアッカーマン関数のほうが増加率が大きいので
グラハム数を...回適用する程度の差は吸収されて、S変換を使った数のほうが大きくなるように感じる。
0307１３２人目の素数さん
2007/08/23(木) 22:33:190308１３２人目の素数さん
2007/08/23(木) 23:29:33ぐらいには上手くまとまってる。
0309１３２人目の素数さん
2007/08/24(金) 01:01:07おかしなところを指摘しておく。
＞タワーa↑↑bはaをb乗するのをb回繰り返す
この書き方だと、a↑↑b=((a^b)^b)^b…=a^(b^b)という意味にとれてしまう。
もしかしたら、「aの○乗というのをb回繰り返す」と言いたかったのかもしれないけど。
＞ack(k,n)はack(k-1,n)と階乗を使って表わせる。
ack(ｋ,n) = ack(ｋ-1,ack(ｋ,n-1))だから、階乗を使って表すことはできないだろう。
＞「じゃあ、俺今まで出た一番でかい関数+1ね。」っていうズルと一緒
ビジービーバー関数の値は他に依存せずに定義されているから、
そういう他に依存した定義をするズルとは違う。
ただ、「計算可能」でないと、他の「計算可能」でない関数と大小比較をするのも難しいし、
具体的な計算手順が分からなくて面白みに欠けるから、このスレではあまり深く扱われないのだと思う。
（ここでいう「計算可能」とは、簡単にいえば、与えられた引数から関数の値を計算するプログラムが書けるということ。）
＞ω(無限順序数のうち最小のもの)が計算可能でないのでズルに思える。
ここで”計算可能でない”と言ってるのは、単にωが「普通の数」ではないという意味だと思う。
ただ、そういう「普通でない数」を使っていても、各順序数に対して定まる関数は「計算可能」であるから、
（例えばH[ω](x)=2xだから、H[ω]は「計算可能」な関数）
ハーディ関数自体はズルではないと言える。
バード数とふぃっしゅ数についてはよく覚えてないので、指摘はしない。
0310たろう
2007/08/24(金) 07:18:44http://www.geocities.co.jp/Technopolis/9946/ambitious.html
X_1(n) ≒ F[ω^3+1](n)
X_a(n) ≒ F[ω^3+a](n)
X_n(n) ≒ F[ω^3+ω](n)
入れ子操作n回 ≒ [ω^3+ω+1](n)
n回回転チェーン↑n(3,3,3) ≒ F[ω^3](n) だから
ほとんど増えていないことに。
0311たろう
2007/08/24(金) 07:41:23Knuthの上矢印 3(↑^n)3 ≒ F[ω](n)
Ak(n, 3) ≒ F[ω](n)
n個のnからなるConwayのチェーン ≒ F[ω^2](n)
チェーンの回転 ↑n (3,3,3) ≒ F[ω^3](n)
バード数の定義の X_n(a) の入れ子操作n回 ≒ F[ω^3+ω+1](n)
5変数Ak ≒ F[ω^4](n)
多変数Ak Ak(n個のn) ≒ F[ω^ω](n)
Ak を２重リストに拡張、Ak([n個のn], [n]) ≒ F[ω^ω^ω](n)
ふぃっしゅ数バージョン５のf5(n) ≒ F[ε_0](n)
0313１３２人目の素数さん
2007/08/24(金) 22:17:39>この書き方だと、a↑↑b=((a^b)^b)^b…=a^(b^b)という意味にとれてしまう
確かに。補足さんくす。
a^b^cはa^(b^c)だな。
^以降では、交換法則が不成立性なのはすぐわかるんだが、結合法則はどうやって示すんだろ
2+2+2=3+3が成り立つから2*3=3*2
2*2*2=3*3が成り立たないから2^3=3^2じゃない
ackについては、もう少し書くと
ack(3,n)=2^(n+3)-3
ack(4,n)=2^(2^n+3)-3
ack(5,n)=2^(2^(2^n+3))-3
↑細かくは間違っているかもしれんがふいんきをつかんでくれ
ack(k,n)とack(k-1,n)を再帰の定義の関係としてでなくて
ack(k,n)の一般項とack(k-1,n)の一般項の関係でみればいい。
つまり、ackは高階原始帰納的関数というわけ
hardy functionに関しては、n<ωの時はこうなるよな？
3(↑^n)3<ω
Ak(n,3)<ω
↑n(3,3,3)<ω
n>=ωの場合は、計算の仕方がわからん・・
>そういう他に依存した定義をするズルとは違う。
違わないと思う。
ttp://www.ice.nuie.nagoya-u.ac.jp/~h003149b/lang/undecidable.html
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:15■ このスレッドは過去ログ倉庫に格納されています