巨大数探索スレッド7
■ このスレッドは過去ログ倉庫に格納されています
0001１３２人目の素数さん
2006/11/19(日) 23:44:01http://www.geocities.co.jp/Technopolis/9946/
前スレ、過去スレ、避難所はこのページからどうぞ。
「前の数＋1」
「1/x x→0」
「∞」
「９を延々と書き続けるプログラム」
「本日からこのスレでは、いっさいの数学的ではない話を禁止する。
私以外で検証する能力を持っている人間はいないようなので、
数学的に明確に証明できた場合以外は反論しないように。
特に今日のような低俗な煽りには徹底して放置で対応すること。」
という類の投稿は放置推奨。
0175もやしっ子
2007/01/23(火) 22:01:16最近はかなり解説が咀嚼されていますので、研究室のHardyと合わせて
読んでみて下さい。ヘボの僕でもVeblenまで追い付くことができました。
些細な疑問でも書いて頂ければ、優しい人が丁寧に教えてくれます。
(他力本願…)
個人的な印象では、リスト関数の解読よりは物量的に楽だと思いました。
変な文字達とお友達になれれば、結構すぐですよ。
0176もやしっ子
2007/01/24(水) 00:11:51＞βへの収束列がβ(n)のとき、α=φ_β(γ)とします。
＞γ=γ'+1のとき、
＞α(n)=φ_(β(n))(φ_(β)(γ')+1)とします。
ここのa(n)がこの形に展開される理屈が分かりませんでした。
値をうまく置き換えてやればφ_β(γ)=αに持っていけるのでしょうか。
0177もやしっ子
2007/01/24(水) 08:28:21どうやって飛ばせばいいですか。
α=φ_ω(1)=ε_1なのかなーと思ったり。
0178もやしっ子
2007/01/24(水) 14:24:04ここではβ=ωとおいて β(n)=n,γ'=0とする。 このとき、
α=φ_ω(1)
α(n)=φ_n(φ_ω(0)+1)
α(0)=φ_0(2)=0^2=1
ここで定義より α=φ_ω(1)=ε_1 なお、このαの収束列は、
1,ε_0,ω^(ε_0+1),ω^ω^(ε_0+1),ω^ω^ω^(ε_0+1),…と続き、
α(0)=1
α(1)=ε_0 そして最終的にnが十分大きいとき
α(n)=(ω↑↑(n-2))^(ε_0+1)となる。
これがα=(ω↑↑ω)^(ε_0+1)=ε_1 の収束列である。
話を α(n)=φ_n(φ_ω(0)+1) に戻すと、
φ_ω(0) = 「すべての ω'< ω に対し φ_ω'(δ)=δ となる δ」 のうち
0番目のもの。 ω'=0 とおくと(ωより小さい順序数は自然数しかない)
φ_0(δ)=ω^δ=δ が得られ、
定義より φ_ω(0)=ε_0 から α(n)=φ_n(ε_0+1) 以上より
φ_n(ε_0+1)=(ω↑↑(n-2))^(ε_0+1) (n<2) 謎のオチ。
0179もやしっ子
2007/01/24(水) 14:49:18文京区シビックセンターの良さげな部屋を借りるツテができたので
2月あたりに近隣の方はゼミごっこしませんか？
メンツが集まらない場合は、素人衆に巨大数をオルグする
イベントに変更となります。いかがでしょう。
僕が暇すぎるのかもしれません。
0180１３２人目の素数さん
2007/01/24(水) 14:58:460181１３２人目の素数さん
2007/01/24(水) 15:14:59φ_ω(1)=ε_1というのは、もしかしてωを1に置き換えてますか？
Hardy functionと違ってφの添え字のωは1に置き換えられません。
φ_ω(0)というのは、φ_0(0), φ_1(0), φ_2(0), φ_3(0), …という収束列の収束先で、
φ_ω(1)というのは、φ_0(φ_ω(0)+1), φ_1(φ_ω(0)+1), φ_2(φ_ω(0)+1), …の収束先です。
0182もやしっ子
2007/01/24(水) 16:01:35えーっと…
φ_ω(1)=「すべての ω'< ω に対し φ_ω'(δ)=δ となる δ」 のうち
1番目のもの …ここですな。
もろに文脈が混線していたようです。
さて、
α=φ_ω(1) のとき
α(n)=φ_n(φ_ω+1) などと性懲りもなくやってますが、
φ_β(γ)そのものが列の収束先そのものとは、全く気付きませんでした。
いやはや。
0183１３２人目の素数さん
2007/01/24(水) 19:59:20都内ならkingも呼ぼうぜ。
0184もやしっ子
2007/01/24(水) 21:55:40いっぺんホワイトボード使ってワイワイやってみたかったのです。
情報や理解も共有することができるかもしれないですし。
往年の功労者諸氏はもう見てないかな…
あと、民間人に巨大数ロマンを植え付けるという企みもあります。
30人くらい入れる部屋とか用意できますが、そんなには来ないでしょう。
2/10を候補日としています。
0185もやしっ子
2007/01/25(木) 12:46:24「集合論入門 無限への誘い」の169,170ページにも「カントールの標準形」
の解説がありました。読み比べてみたところ、それぞれ少し異なる箇所が
あったりしたので適当にまぜて体裁を整えました。
やばかったら指摘してください。たぶん本読んだ方が早いですが。
0でない任意の順序数αは以下のような式に一意に展開することができる。
α=((ω^(β_1))・c_1)+((ω^(β_2))・c_2)+…+((ω^(β_k))・c_k) [kは自然数]
c_1,c_2,…,c_k は正の整数
β_1＞β_2＞…＞β_k はそれぞれ順序数 (β_k=0 でも可)
上式ではωを用いているが、これは「ωを底とした」場合である。
底には2以上の順序数を用いてよい。
このように展開された式を、αのCantor normal formと呼ぶ。
0186１３２人目の素数さん
2007/01/25(木) 15:06:57非可算順序数でも大丈夫なんだ。
0187１３２人目の素数さん
2007/01/25(木) 20:48:180188KingOfUniverse ◆667la1PjK2
2007/01/25(木) 23:04:050189１３２人目の素数さん
2007/01/26(金) 00:39:58任意でおｋです。
0190１３２人目の素数さん
2007/01/27(土) 19:56:56それを和訳すると下のようになります。
ψ(α)は、0とΩ(最小の非可算順序数)から始めて、それ以前に作られた順序数に対し
加法、Veblen関数、ψを繰り返し適用しても作ることのできない最小の順序数である。
ただし、ψはαより小さい順序数に対してのみ適用する。
定義には非可算順序数を用いていますが、定義される順序数は可算です。
これだけだとよく分からないし、具体例はほとんどなかったので、自分なりに解釈してみました。
もしかしたら、間違っているところがあるかもしれませんが。
まず、ψ(0)を考えます。この時点ではまだψは使えないので、加法とVeblen関数だけを使います。
0に対して加法とVeblen関数を使うと、Γ_0未満の順序数をすべて作り出すことができます。
Ωから作った順序数はどれも非加算なので、Γ_0を作り出すことはできません。
なので、ψ(0)=Γ_0ということになります。
次に、ψ(1)を考えます。これは、0とψ(0)とΩに対して加法とVeblen関数を使っても作れない
最小の順序数ですが、これはΓ_1です。同様にして、ψ(α)=Γ_α(ただし、α≦ψ(Ω))となります。
0191１３２人目の素数さん
2007/01/27(土) 19:57:32(>>132,>>136の表記を用いるとφ([2,1],[1,1])と書ける)よりも小さな数はすべて作ることができますが、
φ([2,1],[1,1])は作ることができません。そこで、初めてψ(Ω)を考えます。
ψ(Ω)は、0とΩに加法、Veblen関数、ψを適用しても作ることのできない最小の順序数です。
(ただしΩにはψを適用しない) つまり、ψ(Ω)=φ([2,1],[1,1])です。
ψ(ψ(Ω))を考えると、ψ(Ω)=φ([2,1],[1,1])より小さい順序数に
加法、Veblen関数、ψを適用しても作ることのできない最小の順序数なので、
ψ(ψ(Ω))=ψ(Ω)=φ([2,1],[1,1])となります。
ψ(Ω)≦α≦Ωとしてψ(α)を考えると、ψ(Ω)を使うことはできないので、ψ(α)=ψ(Ω)となります。
なので、次はψ(Ω+1)を考えればいいです。
あとは結果だけ書きますが、>>132,>>136の表記とψを用いた表記を比較すると、
ψ(Ω^Ω^α)=φ([α,1]) (α≧ω)となるようなので、
>>132,>>136の表記ではψ(Ω^Ω^Ω)未満の順序数しか表せないようです。
6-708で出てきたHoward ordinalというのはψ(ε_(Ω+1))だそうです。
ε_(Ω+1)はおそらくΩ^Ω^Ω^…^Ωの収束先です。
0192１３２人目の素数さん
2007/01/28(日) 06:42:53Ω^Ω^Ω=(ω^Ω)^Ω^Ω=ω^(Ω*Ω^Ω)=ω^Ω^Ω=ω^(ω^Ω)^Ω
=ω^ω^(Ω*Ω)=ω^ω^(ω^Ω*ω^Ω)=ω^ω^ω^(Ω+Ω)として、
Ω^Ω^Ω=φ_0(φ_0(φ_0(Ω+Ω)))とすればいいと思います。
非可算順序数を可算順序数と同じように扱っていいのかは分かりませんが。
0193１３２人目の素数さん
2007/01/28(日) 15:07:450194１３２人目の素数さん
2007/01/28(日) 16:08:57ただ(^ω^)を貼り付けたいだけちゃうんかと。
0195１３２人目の素数さん
2007/01/28(日) 17:47:27α=ψ(0)のとき、α_0=φ_0(0), α_(n+1)=φ_(α_n)(0)
α=ψ(β+1)のとき、α_0=ψ(β)+1, α_(n+1)=φ_(α_n)(0)
α=ψ(β)(βは収束列の定義された順序数)のとき、α_n=ψ(β_n)
α=ψ(β)(βは収束列の定義されていない非可算順序数)のときは、
以下の手順で収束列を定める。
まず、βに注目する。
注目する順序数がΩになるまで、以下の手順を繰り返す。
注目する順序数が和のときは、一番右の項に注目する。
注目する順序数がφ_γ(δ)の形のときは、以下のようにする。
δ=0のときは、γに注目する。
δ=δ'+1のときは、δをφ_γ(δ')+1に置き換えてからγに注目する。
その他のときは、δに注目する。
ψ(β)の、注目するΩをxで置き換えた関数をf(x)とする。(f(x)は順序数の関数)
α_0=0, α_(n+1)=f(α_n)とする。
最後の手順を、具体例でやってみます。(かなり複雑な例ですが)
ψ(φ_(φ_(φ_Ω(Ω+Ω))(Ω+2))(0))でやってみると、
まずはφ_(φ_(φ_Ω(Ω+Ω))(Ω+2))(0)に注目します。
( )の中が0なので、添え字のφ_(φ_Ω(Ω+Ω))(Ω+2)に注目します。
( )の中が+1の形なので、Ω+2をφ_(φ_Ω(Ω+Ω))(Ω+1)+1に置き換えて、
添え字のφ_Ω(Ω+Ω)に注目します。
今度は( )の中が0でも+1の形でもないので、Ω+Ωに注目します。
Ω+Ωは和なので、右のΩに注目します。
注目したΩをxに変えると、
f(x)=ψ(φ_(φ_(φ_Ω(Ω+x))(φ_(φ_Ω(Ω+Ω))(Ω+1)+1))(0))
となります。 この関数を入れ子にしたものが収束列となります。
この収束列の定義でHardy functionも使ってF[ψ(Γ_(Ω+1))]という関数を作ると、
ものすごく大きな自然数の関数となるはずです。
ただし、Γ_(Ω+1)の収束列はα_0=Ω+1, α_(n+1)=φ_(α_n)(0)です。
0196１３２人目の素数さん
2007/01/28(日) 17:48:07可算順序数の関数から巨大な可算順序数を作り、可算順序数から巨大な自然数の関数を作り、
自然数の関数から巨大な数を作るということになります。
Ωを可算順序数の変数で置き換えるのと、ωを自然数の変数で置き換えるのには共通点も見られます。
今やっていることがよく分からないという気持ちも分かります。
具体的に計算しようにも巨大すぎて、現実には計算できないような数を扱っているし、
主題は数→自然数の関数→順序数→可算順序数の関数と、どんどん普通の数から離れてきているので。
ただ、作られていく数はどんどん巨大になってきています。
一つ残念なのは、このスレの住人がこれまでにないような巨大な数を作り出したと思っても、
いつもそれを上回る巨大な数を作り出す方法が既に数学界に存在しているということです。
上で述べた関数も、Hardy functionと英語版Wikipediaのψ表記を組み合わせただけなのに、
このスレで作られた関数の中ではふぃっしゅ数ver.4を除くどの関数よりも大きいわけです。
(ふぃっしゅ数ver.4はBBを用いて作られた、定義可能だが計算不能な数なので別格ですが)
それでも、巨大な数の作り方を紹介していくというだけで十分意味のあることだと思いますが。
0197１３２人目の素数さん
2007/01/29(月) 23:15:55ゼミは本当にやるのかな？はたして、このスレの
住人は何人くらい集まるか？
素人衆向けの企画ならば、素人衆として参加します。
実際に素人衆だし。
0198もやしっ子
2007/01/30(火) 03:18:41部屋はすでに取ってあります。2/10午後、文京シビックセンター会議室です。
初心者と熟練者の議論のギャップをどう埋められるか、という。
とりあえずその日程オッケーみたいな方は、ここで点呼してみて下さい。
5人も集まれば、十分に時間が潰せると思います。たぶん。
0199１３２人目の素数さん
2007/02/01(木) 00:07:15英語ならHoward ordinalの定義について書いてある論文は結構見つかるのですが、
分かりやすかったものは、Veblen関数の応用で、
φ_α[Ω](β):=φ_α[γ](0)=γとなるγのうちβ番目のもの
とします。例えば、φ_Ω(0)=Γ_0、φ_(Ω+1)(0)=Γ_Γ_Γ_……となります。
以降はCNFと同様に、
Ω^α_0*β_0+Ω^α_1*β_1+Ω^α_2*β_2+……
（ただしα_0>α_1>α_2>……, Ω>β_i）
とすれば、φ_α(β)の有限和でHoward ordinalより小さいすべての順序数を表記できます。
0200１３２人目の素数さん
2007/02/01(木) 00:27:09A(α):=ω^α（Ω>α）
A(α[Ω]+β):=A(α[γ])=γとなるγのうちβ番目のもの
例えば、
A(Ω)=ε_0
A(Ω*α+β)=φ_α(β)
A(Ω^2)=Γ_0 です。
もちろんA(ε_(Ω+1))とかもできますがさらに上の基数を使って、
B(α):=Ω^α
B(α[ω_2]+β):=B(α[γ])=γとなるγのうちβ番目のもの
とすれば、A( B(ω_2) ) = A( ε_(Ω+1) ), A( B((ω_2)^2) ) = A( Γ_(Ω+1) )
となってHoward ordinalよりも大きい順序数を作ることができます。
しかし、この方法だとA(Ω),A(B(ω_2)),A(B(C(ω_3))),A(B(C(D(ω_4)))),………
という列の極限順序数が限界で、以降のうまい定義がなかなか難しいのですが・・・
0201１３２人目の素数さん
2007/02/01(木) 00:29:34http://web.mit.edu/dmytro/www/other/OrdinalNotation.htm
0202１３２人目の素数さん
2007/02/01(木) 02:23:36ψ_α(β)は、0に対して加法、Veblen関数、ψを繰り返し適用しても
作ることのできない、濃度がω_α(α番目の無限基数)の最小の順序数である。
ただし、ψの添字として用いる順序数を除いては、ψはβより小さい順序数にのみ適用する。
最後の行では、例えばψ_[ψ_0(1)](0)=ψ_[ψ_0(1)](1)＜ψ_[ψ_0(1)](2)のような
不自然なことを起こさないために、添字ではψを自由に使えるようにしてあります。
濃度に関しては、次の性質だけ理解しておけば十分だと思います。
ω以上の順序数には、濃度として一つの無限基数が対応する。
可算順序数の濃度は、ω(=ω_0)である。
α＜βならば、濃度ω_αの順序数＜濃度ω_βの順序数である。
濃度ω_α以下の順序数の収束列は、濃度ω_α以下の順序数に収束する。
最後の行は、「以下」であって「未満」ではありません。
例えば、ω_nはω_ω未満の順序数の収束列ですが、ω_ωに収束します。
添字付きψで定義される最大の非可算順序数はω_ω_…_0の極限です。
この順序数を仮にΨと書くことにすると、
添字付きψで定義される最大の可算順序数は、ψ_0(Ψ)となります。
0203１３２人目の素数さん
2007/02/01(木) 02:24:11α=ψ_0(0)のとき、α_0=φ_0(0), α_(n+1)=φ_(α_n)(0)
α=ψ_β(0)のとき、α=ω_βであり、
βに収束列があるときはα_n=ω_(β_n)となる。
α=ψ_β(γ+1)のとき、α_0=ψ_β(γ)+1, α_(n+1)=φ_(α_n)(0)
α=ψ_β(γ)(γは収束列の定義された順序数)のとき、α_n=ψ_β(γ_n)
α=ψ_β(γ)(γは収束列の定義されていない非可算順序数)のときは、
以下の手順で収束列を定める。
まず、γに注目する。
注目する順序数がψ_[δ+1](0)の形になるまで、以下の手順を繰り返す。
注目する順序数が和のときは、一番右の項に注目する。
注目する順序数がφ_ε(ζ)の形のときは、以下のようにする。
ζ=0のときは、εに注目する。
ζ=ζ'+1のときは、ζをφ_ε(ζ')+1に置き換えてからεに注目する。
その他のときは、ζに注目する。
注目する順序数がψ_ε(0)の形のときは、εに注目する。
γの、注目するψ_[δ+1](0)をxで置き換えた関数をf(x)とする。
α'_0=0, α'_(n+1)=ψ_δ(f(α'_n))とし、
収束列はα_0=0, α_(n+1)=ψ_β(f(α'_n))とする。
（つまり、最後だけはψ_βを適用し、それ以外はψ_δを適用する）
Ψ_0=0, Ψ_(n+1)=Ψ_[Ψ_n](0)
Hardy functionや、上記の順序数の計算のできるプログラムをRubyで作ってみました。
Rubyはttp://arton.hp.infoseek.co.jp/indexj.htmlからインストールしてください。
ttp://www.uploda.net/cgi/uploader4/index.php?file_id=0000009755.lzh
解凍するとLarge_number.rbというファイルがあるので、
これをメモ帳などで開くと初めの方に使い方が書いてあります。
0204１３２人目の素数さん
2007/02/01(木) 21:15:13ＧＪ！ありがたく使わせていただきます。
0205１３２人目の素数さん
2007/02/01(木) 22:53:49ttp://www.uploda.net/cgi/uploader4/index.php?file_id=0000009781.lzh
0206１３２人目の素数さん
2007/02/02(金) 20:17:08たとえば、ω^φ_1(0)=ω^ε_0=ε_0=φ_1(0)ですが、
F[ω^φ_1(0)](2)とF[φ_1(0)](2)は違う結果になります。
また、>>190の定義からすればψ(ψ(Ω+2))=ψ(Ω)＜ψ(Ω+1)ですが、
F[ψ(ψ(Ω+2))](2)＞F[ψ(Ω+1)](2)となってしまうはずです。
ただ、普通に使う分には問題はないと思います。
0207１３２人目の素数さん
2007/02/02(金) 21:15:56>>130-131
0208１３２人目の素数さん
2007/02/02(金) 23:09:45>>130-131みたいに収束列の異なる順序数は別物という見方をすれば
前者は問題ないのは分かってます。
後者に関しては、>>190での定義によるψと、
>>195の収束列から定義されるψが全く同じではないのが原因です。
数学的に厳密に言うのならば、Hardy functionに使っているものは
極限順序数ではなく、「収束列」です。ここでいう「収束列」は、
”自然数か「収束列」の列”として再帰的に定義できます。
ただ、「収束列」は列の収束先の極限順序数と対応づけることができ、
順序数の大小とHardy functionの増加度の大小には関連性があるので、
極限順序数と「収束列」を普段は同一視しているわけです。
でも、極限順序数と「収束列」は違うものであるため、>>206の前者のような問題が生じます。
>>131で「極限順序数と収束列は一対一に対応する」と言ってしまったのは不正確で、
極限順序数と「収束列」は一対多に対応します。
「収束列」と一対一に対応する（正確には「一対一対応させている」）のは、「極限順序数の表記」です。
>>205のプログラムが計算しているのは順序数ではなく、「収束列」です。
>>206で「プログラムが正確に計算してない」といったのも不正確ですね。
不正確だったのは定義の方であって、プログラムの計算が不正確なわけではありません。
0209１３２人目の素数さん
2007/02/04(日) 02:30:22999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
0210１３２人目の素数さん
2007/02/04(日) 02:40:110211１３２人目の素数さん
2007/02/04(日) 03:10:09=ω（=´ω`=）^ω^(Ω*Ω)=(^ω^)(^ω^)(^ω^)(o^Ω^o)=ω^ω^ω^ ^^ ^^
0212１３２人目の素数さん
2007/02/05(月) 18:39:050213１３２人目の素数さん
2007/02/09(金) 17:23:520214１３２人目の素数さん
2007/02/10(土) 01:37:030215もやしっ子
2007/02/10(土) 09:17:59ちゃんと準備して。
0216KingOfUniverse ◆667la1PjK2
2007/02/10(土) 20:05:540217五劫の擦り切れ
2007/02/11(日) 02:56:43「グラハム数」のグラハム博士って、電話発明したグラハム・ベルと親戚？
ゼミ後に検索してみたら「秋山仁」やら「ベル研究所」がヒットしますが…
0218１３２人目の素数さん
2007/02/11(日) 08:03:49別にしんせきじゃねえんじゃね。
0219１３２人目の素数さん
2007/02/12(月) 07:05:12AMSの会長をやってたこともある人。
秋山仁と日本語の離散数学の入門書も出してるね。
時代が全然違うからあまり「親戚」とは言わないんじゃないかなあ。
Ronald Lewis Graham (born October 31, 1935)
Alexander Graham Bell ( March 3, 1847 ? August 2, 1922 )
http://en.wikipedia.org/wiki/Ronald_Graham
http://en.wikipedia.org/wiki/Alexander_Graham_Bell
http://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AC%E3%82%AF%E3%82%B5%E3%83%B3%E3%83%80%E3%83%BC%E3%83%BB%E3%82%B0%E3%83%A9%E3%83%8F%E3%83%A0%E3%83%BB%E3%83%99%E3%83%AB
たぶん親戚関係は無いんじゃないの。日本の田中さんとかと同じで。
0220１３２人目の素数さん
2007/02/16(金) 16:58:370221１３２人目の素数さん
2007/02/16(金) 16:59:150222１３２人目の素数さん
2007/02/23(金) 15:22:030223１３２人目の素数さん
2007/03/05(月) 17:53:040224１３２人目の素数さん
2007/03/11(日) 18:19:180225１３２人目の素数さん
2007/03/18(日) 12:56:590226１３２人目の素数さん
2007/03/28(水) 23:37:18大して進展はないのかな？
今のところチャンピオンは前スレの >>863 か。
0227１３２人目の素数さん
2007/03/29(木) 02:16:03863 ：通りすがり：2006/08/29(火) 21:34:51
>>440-441 をちゃんと書いてみた。
チューリングマシンのままじゃ扱いにくいので、
今のコンピューター風命令にした。
ついでに拡張も。
http://free.gikoneko.net/up/source/up124719.txt
0228１３２人目の素数さん
2007/03/29(木) 02:31:01440 ：通りすがり：2006/03/09(木) 18:27:05
●STEP0
比較的単純なマシンモデル（チューリングマシン）を定義することで、
どのような帰納的定義の関数よりも早く増大する関数、ビジービーバー関数が定義出来た。
ビジービーバー関数は「どのような帰納的定義の関数よりも早く増大する関数」の中ではほとんどＭＩＮの関数である。
BBに帰納的拡張をしていくことである程度大きくすることは可能。、
（BB^n(2)やBBのふぃっしゅ数的拡張など）
●STEP1
チューリングマシンにビジービーバーの値を返す動作を追加したマシンを考えてみる。
厳密にはたとえば、
各ステートの動作定義に１ビット加え、このビットが立っていたら
BB(テープ上のヘッド位置から右に続く１の数)個の１をヘッドの右側に書き込むという動作で良い。
このマシンｎステートでセット可能な１の数の最大をBB2(n)とすると、
この関数はビジービーバー関数に通常の多重帰納的定義を用いて拡張したどんな関数よりも早く増加する。
（BBのふぃっしゅ数的拡張もBB2に及ばない）
一般に、
『チューリングマシン＋関数f』のマシンｎステートで
セット可能な１の数の最大をBB｢f｣(n)とする。
BB｢f｣ は、fに通常の多重帰納的定義を用いて拡張したどんな関数よりも早く増加する。
BB｢恒等変換｣ = ビジービーバーであり、
BB｢ビジービーバー｣ が上の BB2 である。
BB｢f｣の｢｣の中に関数を入れることで新たな関数ができ、
帰納的定義の関数のように帰納的にBB｢f｣の定義が可能である。
0229１３２人目の素数さん
2007/03/29(木) 02:31:38●STEP2
STEP1の方法でマシンの帰納的定義を行っていけば大きい関数が作成できるが、
この方法にも限界がある。
この限界を超える為にはチューリングマシンに以下のような機能追加が必要である。
１．自然数から自然数への関数をテープに読み書きできる（可算無限のデータ量）
２．テープに関数の初期値（恒等関数で良い）をセット出来る
３．関数fからBB｢f｣をつくることが出来る
４．関数の値を返せる
といった感じであろうか。
（厳密な定義は他の人に任せる）
このようなマシンｎステートで表現できる最大の数をCC(n)とする。
これはいわば「STEP1の帰納的拡張をｎ文字以内で一番効率よく行った場合の数」
のようなものであり、CC(n)はBB｢｣のどんな帰納的拡張よりも早く増大する。
●STEP3
さらなる拡張はやはりマシン自体を定義できるようなマシンということになるだろう。
矛盾がおこらないような定義で最良のものはどんな感じになるのかな？
0230通りすがり
2007/04/06(金) 23:12:40あるチューリング完全マシンをMachine[0],
Macihne[0]のn命令のプログラムで表現可能な最大の数をM[0](n)とすると、
M[0](n) ≒ BB(n)
Machine[0] の停止問題を解く命令をhalt[1],
Machine[0] に halt[1] の命令を追加したマシンを Machine[1],
Macihne[1]のn命令のプログラムで表現可能な最大の数をM[1](n)とすると、
M[1](n) は 前スレ >>863 の mm(n) を大きく超える。
Machine[a]のｎ命令のプログラムで表現可能な最大の数をM[a](n)
Machine[a] の停止問題を解く命令をhalt[a+1]
Machine[a] に halt[a+1] の命令を追加したマシンを M[a+1]
としてM[a]を定義することが出来る。
halt[a] を 「b<a となるすべてのマシン Machine[b] の停止問題を解く命令」としても同じであり、
この定義にすると、a を順序集合に拡張できるようになる。
M[ω](n), M[ω^ω](n), M[Γ_0](n) などが定義できる。
0231１３２人目の素数さん
2007/04/08(日) 14:42:10> 前スレ >>863 の mm(n) を大きく超える
前スレ >>863 のプログラムが見えないので、どこかにアップしてもらえますか。
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) に比べて革命的に大きくなっているように見えたんですが、
だんだんと普通の拡張に見えてきました。
プログラムも２倍程度に増えただけですし。
■ このスレッドは過去ログ倉庫に格納されています