巨大数探索スレッド13
■ このスレッドは過去ログ倉庫に格納されています
ε_0まではBEAFと同じ。
テトレーション空間の区切りを.={1´2}={1{1,,2}2}で表す。しかし{n,n{1{1,,2}2}2}みたいな表記はvalidでない。
{n,n{1,,2}2}={n,n{1´2}2}=ε_0
{n,n{1,,2}3}=ε_0*2
{n,n{1,,2}1,2}=ε_0*ω
{n,n{1,,2}1{1,,2}2}=ε_0^2
以下、{n,nA2}のAの部分だけ書く
{2,,2}=ε_0^ω
{3,,2}=ε_0^ω^ω
{1{1{1,,2}2}2,,2}={1{1´2}2´2}=ε_0^ε_0
{1{1{1{1,,2}2}2{1,,2}2}2,,2}
={1{1{1´2}2´2}2´2}
=ε_0^ε_0^ε_0
{1{1{1,,2}3},,2}={1´3}=ε_1
{1{1{1,,2}4},,2}={1´4}=ε_2
{1{1{1,,2}1{1{1,,2}2}2},,2}
={1´1{1´2}2}=ε_ε_0
{1{1{1,,2}1{1,,2}2}2,,2}
={1´1´2}=ψ(Ω)
{1{1{1,,2}1{1,,2}1{1,,2}2}2,,2}
={1´1´1´2}=ψ(Ω^2)
{1{1{2,,2}2}2,,2}=ψ(Ω^ω)
{1{1,,2}2,,2}=ψ(Ω^Ω)
{1{1{1,,2}2,,2}2,,2}=ψ(Ω^Ω^Ω)
{1,,3}=ψ(ε_{Ω+1}) 修正
{n,n{1,,2}1,2}=ε_0*ω+1
{1{1{1,,2}1{1,,2}2}2,,2} ={1´1´2}=ψ(Ω)+1
{1{1{1,,2}1{1,,2}1{1,,2}2}2,,2} ={1´1´1´2}=ψ(Ω^2) +1
評価はFGH 強配列表記もBEAFを元にしてるけど
それとは何が違うんだ? >>779
普通にHardyと順序数を使った物に対して
どの辺がメリット? すみません
聞き方が悪かったですね
バシク行列やBEAFが最終的に出力するものは
実数?
帰納的順序数?
帰納的ではない可算順序数?
非可算順序数? なんでそこが疑問なんだ?
>>779の書き方が誤解を招くといいたいのか? >>780 修正の修正
{1{1{1,,2}1{1,,2}2}2,,2} ={1´1´2}=ψ(Ω)
{1{1{1,,2}1{1,,2}1{1,,2}2}2,,2} ={1´1´1´2}=ψ(Ω^2)
この二つの式に+1はいらなかった。たびたびスマン カントール標準系を総和の多重再帰で表現したらBEAFのもう一つの表現が出来そうなんだが何となくイマイチ >>784
バシク行列もBEAFも自然数を出力します。
その関数部分の強さを表すのに帰納的順序数が使われます。(帰納的でなく再帰的と言いたい)
>>783
Hardyと順序数を使った物というのがよくわかりませんが、原始数列から拡張されているシステムを指すのであれば、とくにメリットがあるとは感じません。
>>781
BEAFはテトレーション空間の配列以降がいまひとつ活用できてません。うまいこと定義を修正してもpDANのアイディアには根本から及ばない感じです。
>>777
セパレータ(分離子と訳せばいい?)の強さのようなもので、順序数崩壊関数で大きな順序数を崩壊させるように使います。
1{1,,2}2 を崩壊させると、一例だけど
1{1{1,,2{1,,2}2,2}2}2
になったりするような。 いまいち記述の意味がわからない
>>779 などに書いてあるのは
左辺は自然数、右辺は順序数
左辺が関数であれば、
その増加度をHardy階層の順序数で表している
というのならわかるのだが
左辺は自然数、となると右辺の順序数は何を表している?
その辺を一行だけでいいので省略しないで書いていただけると なんとなくわかってきた
{n,n{1,,2}3}=ε_0 の意味は
{n,n{1,,2}3} ≒ F_(ε_0*2) (n)
の事で
{2,,2}=ε_0^ω
の意味は
{n,n{2,,2}2} ≒ F_(ε_0^ω) (n)
の事であってる?
Aの部分は帰納的順序数の表記法にもなっている?
つまり、
例えばこの記述法で ψ(ε_{Ω+1}) 以下の全ての順序数を表現できる? 多変数最大シフト数関数
強さ:f_[{ω^CK_1}^{ω^CK_1}](n)
・チューリングマシンを既知とする
・s(M) = E_n に含まれる全ての M について、停止するまでに M がシフトする回数
・S(n) = max{s(M)|M∈E_n} 初期テープ状態が全て0である、
あらゆる n-状態 2-記号チューリングマシンの中で最大のシフト回数
・m,a = 0以上の整数
・X = 0個以上の0以上の整数
・a#m = m個のa
・S[](n) = S(n)
・S[0#(m+1)](n) = S[n#m](n)
・S[X, a+1, 0#(m+1)](n) = S[X, a, n#(m+1)](n)
・S[X, a+1](n) = 初期テープ状態が、S[X, a](1), S[X, a](2), S[X, a](3), ...... の位置を1、他は0である、
あらゆる n-状態 2-記号チューリングマシンの中で最大のシフト回数 多重リスト化してε^CK_1にすればゴミービーバーでなくなる? 自然数上の任意の計算不能関数f(x)について、健全性(soundness)と実効性(effectiveness)
をもつ論理体系のもとでは、f(n) = 0, f(n) = 1, f(n) = 2,...,f(n) = i,...のいずれも
証明不能となるような自然数nが少なくとも一つは存在する。(*)
(証明)健全性と実効性をもつ論理体系では、その中で証明可能な式全体の集合が帰納的可算集合
になるため、もし任意のnについてf(n) = 0, f(n) = 1,...のいずれかが証明可能な式なら、
あるアルゴリズムで任意のnについてf(n)が求まることになりfの計算不能性に矛盾。
したがってf(n) = 0, f(n) = 1,...のいずれも証明不能となるnが存在する。(終)
しかしこの結論はビジービーバー関数などの計算不能関数がwell definedであることと矛盾しない。
P(n, m) ⇔ mはn状態ビジービーバーゲームの優勝者が出力する1の個数 + 1
として、∀n∃mP(n, m) ∧ ∀n∀x∀y((P(n, x) ∧ P(n, y)) ⇒ x = y)が証明可能なため、
ビジービーバー関数はwell definedである。すなわち、公理のどのモデルでも任意のnについて、
モデルさえ決まれば、Σ(n)の値が一意に決まる。
(*)はf(n) = 0, f(n) = 1,...のうちどれが真か、またはどれも偽かが、同じ公理の上でも
モデル間では異なるかもしれない可能性を示しているだけである。
また、"少なくとも一つは"と書いている通り、Σ(4)までの値が計算できることと(*)も矛盾しない。
ゲーデルの完全性定理から、もし一階述語論理による公理のもとであれば、
Pが証明不能 => Pが恒真でない => Pを偽とするモデルが存在する
から、(*)よりf(n) = 0を偽とするモデル, f(n) = 1を偽とするモデル,...のいずれもありえる。 ∀n∃mP(n, m) ∧ ∀n∀x∀y((P(n, x) ∧ P(n, y)) ⇒ x = y)が証明できただけじゃwell definedとは言い切れないんじゃ。
異なる解釈で異なる関数を読み取ることができても成り立つから ビジービーバー関数がwell definedでないとは言わない >>795
φ(0), φ(1), φ(2), ....,,, が全て個々に証明可能だとしても
∀n φ(n)が証明可能だとは限らない。
(例えばφ(n)を、nは矛盾の証明のゲーデル数ではない、
などとすればその例になる。)
∀n φ(n)を証明するには、φ(x)をxの値によらない
“一様な”方法で示してから全称量化しないといけない。
だから上に書いてある議論はおかしい。
busy beaver関数が計算可能じゃないのは、
実際には停止しない或るチューリングマシンTについて、
その非停止性が証明できないからだよ。
だからPeano算術なり何なりのベースの理論に
このTがm stepで停止する、という公理を付け加えると
ノンスタンダードな理論になる。
この理論のモデルの中では、Tが或る超準自然数mについて
m stepで停止するように見えている。 証明可能とか以前に、ちゃんと定義しようよ
ふぃっしゅ数とかラヨ数とか
定義になってないものが定義として扱われて非常に違和感 >>796確かに「>>796の思う」well definedの定義とは一致しないかもね。
>>798「だから」の前後が全然つながってない件 >>795というかこれで証明のつもり?はしょりすぎだろ。 >>800
ごめん、完全性定理とか不完全性定理とか
算術の超準モデルの基本とかが
俺の脳内で勝手に一般常識みたいな扱いになってた
発表下手な人のパターン 関数を一意に定義できてなくてもwell definedでいいの? とりあえず1階述語論理で非停止性を証明することはできるよな。停止性を証明できたとしても超準ステップ数目で停止することを示している可能性を排除できない、
という意味であって ZFCが無矛盾だとしてもZFC+¬Con(ZFC)のモデルが存在するのと似てる。ω矛盾しておりすべからく超準モデルになる もちろん出来るものもあるし、
本当は停止するのにその事を証明できないような
マシンもある 一階述語論理で非停止性を示すというのは、
どういう公理の下での話を想定してるの?
一階述語論理というのは¬とか⇒とか∀とかの
命題結合記号や量化記号を扱えるだけのシステムなので
A⇒Aとか(A∧B)⇒Aみたいなトートロジーを示せるだけで、
具体的な自然数やチューリング機械には
そもそも言及する事自体できないのだけど。
仮にZFCみたいな理論を公理に採用し
(て適切にチューリング機械の理論を解釈し)
たとしても、
実際に停止するマシンについては、
停止するまでのマシンの挙動を書き下すだけで
停止性の証明が出来るわけだから
任意の非停止マシンについて、非停止を示せるのなら、
停止問題が解ける事になって不合理でしょ。 >>808
ごめん、よく自分のレス見たら書き間違えてた、、
×本当は停止するのに
○本当は停止しないのに 可算無限集合の冪集合の濃度=連続体濃度がZFCのモデルによってアレフ1だったりアレフ2だったりするが、冪集合をとる操作がwell definedでないとか、一意ではないとは普通言わないな。 >>793
計算不可能レベルで再帰定義を取り入れるのがあまり歓迎されない。
引数nに応じてn-ビジービーバー関数をオラクルで呼び出すシステムを取り入れるだけくらいでいい 何か凄い初歩的で申し訳ないんだけど、
〜〜〜〜で決まる何とか函数がwell-definedである事を
言うためには、〜〜〜〜という記述が表わす対象が
一意に決まる事を言わないといけないんじゃないの?
〜〜〜〜が関数になっている事ではなくて。 モデルによって関数が異なる(ある標準的な自然数nについてf(n)の値が異なる)場合はwell definedとは普通言わないと思う >>813の場合はアレフ1やアレフ2がwell definedでないということ >>817言い方が悪かった。べき集合の濃度がwell definedでない >>816
まあラヨ関数についてはそれで良い気がするけど、
だとすると、何かコーディング決めて
f(n)
:=m(自然数nのコードするチューリング機械が
mステップで停止する場合)
:=-1 (nのコードするチューリング機械が停止しない場合)
:=-2 (自然数nがチューリング機械をコードしない場合)
とすると、f(n)=-1という関係がwell-definedで
なくなり得る気がする >>819
ZFCが無矛盾だとして(ZFCじゃなくてもいいけど)、nをZFCが矛盾するという証明列を見つけ出して停止するチューリングマシンのコードとすると、
超準モデルで考えるとf(n)は超準的自然数を返すが標準モデルで考えると-1を返す。
とか? 定義文で関数を強くするよりも、定義文を上位の定義文で拡張すれば良いのでは
中の定義文を強化する言わばS定義文 >>820
だいたいそんな感じ。
そしてそれは標準的な入力に対しても起こり得る。 >>795はビジービーバーがwell definedであることの説明になってないと思うし
関数であることや全域性を証明できてもモデルによって関数が変わるってつまりwell definedじゃないってことだしだからこそラヨ関数がwell definedでないと主張してたんじゃないかと
ビジービーバー関数もラヨ関数も任意のモデルで停止するとか命名文になるとかいうふうにすれば解決する、
というのであって
ラヨ関数は「任意の」という量化の範囲を公理のモデルにするか命名文のモデルにするかで2パターンに別れる とりあえず集合の濃度すらwell definedでないと思うなら、数学においてwell definedとはどんな意味の用語なのか調べたほうがいいんじゃないかな。
多分思ってる定義と世間一般での定義が違うから。 >>826はwell definedとはcomputableのことだと誤解してる
数学を知らぬ馬鹿の典型 >函数がwell-definedである事を 言うためには、
>(函数の)記述が表わす対象が 一意に決まる事を
>言わないといけないんじゃないの?
それは函数を定義する体系の強度に依存する
そういうことに無神経なのが、数学を知らぬ馬鹿 逆に>>830が考えるwell definedといえるものって例えば何? 集合の濃度がwell definedでないというんじゃなくて、べき集合の濃度というだけじゃどれほどの濃度かはwell definedじゃないという意見 モデルの取り方によって値が超準元になり得るというのは
ごく普通にあり得る現象で、普通に数学をしている場合は
それだけだwell definedでないとは言わないとは思う。
ただ、仮に標準的自然数の値のみを考えるとか
規約したとして、それで元々の問題においてきちんと
数を定義した事になるのかと言えば大変微妙なんだけど。
つまり、ある式が或る自然数を定義しているかどうかが
ZFC + 巨大基数公理みたいな死ぬほど強い公理系から
独立になってしまうので。 だから冪集合の濃度がwell definedでないという
言い方は普通しないよね。
2^aleph 0 = aleph αとした時に、αの値は
ZFCでは決定できない、とは言えるけど。
すごく単純な例で例えていうなら、
世の中にはアーベル群と非アーベル群があるから
群Gが可換かどうかはwell definedでない、
とか言ってるようなもの。 2*3*5*√(x^2+1/2^2+1/3^2+1/5^2+2*(x*(1/2+1/3+1/5)+1/2*(1/3+1/5)+1/3*1/5))
2*3*5*√(4^2/5^2+1/2^2+1/3^2+1/5^2+2*(-4/5*(1/2+1/3+1/5)+1/2*(1/3+1/5)+1/3*1/5))=7
2*3*5*√(2^2/3^2+1/2^2+1/3^2+1/5^2+2*(-2/3*(1/2+1/3+1/5)+1/2*(1/3+1/5)+1/3*1/5))=11
2*3*5*√(3^2/5^2+1/2^2+1/3^2+1/5^2+2*(-3/5*(1/2+1/3+1/5)+1/2*(1/3+1/5)+1/3*1/5))=13
2*3*5*7*√(5^2/5^2+1/2^2+1/3^2+1/5^2+1/7^2+2*(-5/5*(1/2+1/3+1/5+1/7)+1/2*(1/3+1/5+1/7)+1/3*(1/5+1/7)+1/5*1/7))=37
2*3*5*7*√(6^2/5^2+1/2^2+1/3^2+1/5^2+1/7^2+2*(-6/5*(1/2+1/3+1/5+1/7)+1/2*(1/3+1/5+1/7)+1/3*(1/5+1/7)+1/5*1/7))=5
2*3*5*7*√(7^2/5^2+1/2^2+1/3^2+1/5^2+1/7^2+2*(-7/5*(1/2+1/3+1/5+1/7)+1/2*(1/3+1/5+1/7)+1/3*(1/5+1/7)+1/5*1/7))=47
2*3*5*7*√(5^2/7^2+1/2^2+1/3^2+1/5^2+1/7^2+2*(-5/7*(1/2+1/3+1/5+1/7)+1/2*(1/3+1/5+1/7)+1/3*(1/5+1/7)+1/5*1/7))=97
2*3*5*7*√(6^2/7^2+1/2^2+1/3^2+1/5^2+1/7^2+2*(-6/7*(1/2+1/3+1/5+1/7)+1/2*(1/3+1/5+1/7)+1/3*(1/5+1/7)+1/5*1/7))67
2*3*5*7*√(8^2/7^2+1/2^2+1/3^2+1/5^2+1/7^2+2*(-8/7*(1/2+1/3+1/5+1/7)+1/2*(1/3+1/5+1/7)+1/3*(1/5+1/7)+1/5*1/7))=7 どのモデルでもその中でBB(n)は一意であることも、どの計算可能関数よりも大きいことも証明できるんだから単に大小比較をするのに何の問題もないじゃないか。
0=BB(n),1=BB(n),...のどれかが証明できる必要なんてない。 BBの大きさを語る能力の無い公理系では
BB(ある大きい数) の値を実際とは違う値だと決めても矛盾を証明出来ない
だから上の公理系に対して
BB(ある大きい数)=実際と違う値
という公理を加えても無矛盾となる
だからBB(ある大きい数)の値は公理依存で一意に決まらない
と主張してる人がこのスレに約1名いる それぞれのモデルの中で一意に定まるんじゃなくて、定義文から一意に定まることを求められるんだと思う、でないと数の大小関係が自明でなくなってしまうことが考えられるし、ある定義文がどこまでも大きな自然数を定義しているという主張ができてしまう。
同じ体系内であればどう解釈しようが大小関係は変わらないということも考えられるが異なる解釈で大小が変わってしまうことがあるのは評価の一意性に欠けてしまう。
あと函数を定義する体系の強度に依存するというのは、たとえば1階述語論理で定義された場合であれば体系の強化が間違っていることになってこの例には当てはまらない
ビジービーバー関数は任意のモデルで同じ関数を意味するように定義することができないという意味では1階述語論理で定義できないが、
任意の標準モデルを充足するという形でなら、同じ関数を意味するように、つまりwell definedに定義できる 任意のモデルで同じ関数を意味するって
自然数を定義できないモデルとかどうすんの? 何かstackexchangeとか見てたら、やっぱRayo関数は
いろいろ問題ありそうな感じだね。
海外サイトでも有名な論理学者とかが、やっぱり
理論の不完全性定理とかTuring機械の停止性とかと
絡めて説明してるからこのスレが脱線して非本質的な
議論してるわけじゃなさそう。
https://math.stackexchange.com/questions/2199190/the-first-few-values-of-rayos-function
Rayo関数は一階の集合論内では定義できない。
二階の集合論とかMorse-Kelleyの集合論とかは
一階部分の真理述語を持ってるから一応定義は出来る。
更にRayo関数がZFCなどの一階の集合論で定義出来る
全ての関数を十分先でdominateする事が示せる。
真理述語が使えるのかどうかとかの基礎論的な文脈を
特定しないと無意味なんじゃないのか、と。
二階の集合論が必ず一階部分の真理述語を
持ってるわけじゃないし、持ってなくても部分関数で
代用できる場合もあるし、さらに関数が集合として
存在する事が示せなかったりするし云々。
ぶっちゃけ、連続体濃度がアレフkとなる
自然数nが存在する時k、存在しない時0、みたいな定義も
明らかに1 googol文字以下で出来てるんだか
こういうのどうすんのよ、と。R(n)の値はちょっと先に
行くと明らかにZFCから独立になって
本質的にメタ数学的な問題だらけになる、と。
https://mathoverflow.net/questions/34710/succinctly-naming-big-numbers-zfc-versus-busy-beaver
何か計算量理論で出てくるアルゴリズムで
有名な研究者がコメントしてたりする。
https://mathoverflow.net/questions/32891/finding-the-largest-integer-describable-with-a-string-of-symbols-of-predefined-le
基本的に、こういうコンテストでは誰が勝者かは
再帰理論的な意味で計算不可能になる。
何気にFields賞受賞者とか、証明論の有名な研究者とかがコメントしてる。 あとどっかに、超準モデルでは超準ステップで停止する
Turingマシン、みたいな問題を避けるためには
ベースの理論が無矛盾なだけじゃなくて
少なくともω無矛盾じゃとないといけない、
とか書いてあって、確かにそうだよね、と。
停止までのステップ数が変なモデルを取ると
変わり得るというのは、こういう或る程度の強さの
算術的な健全性を仮定すれば一応解決出来るっぽい。
標準的な自然数というのは一通りに確定する事になってるから。 二階論理なら自然数のモデルが全部同型になるような自然数論を作れるのは確かにデデキントが証明した通り。
しかし英語版wikipediaのPeano axiomsの記事
https://en.m.wikipedia.org/wiki/Peano_axioms
によると、これは集合論の立場から見れば、集合論のモデルが決まればその中での二階PAのモデルは一意と言っているだけで、選んだ集合論のモデルが超準的ならその中で作れる二階PAのモデルもまた超準的でありえる。 >>837
BB(ある大きい数)がある値「である」と仮定しても無矛盾、と
BB(ある大きい数)がある値「ではない」と仮定しても無矛盾、じゃ意味が違うぞ。
後者は見たことあるが、前者の主張は見たことないな。明らかにBB(ある大きい数)=0からは矛盾が導けるし。 言いたいことが>>798ですでに言われていた
任意の標準的な自然数につき、ビジービーバー関数の値でないことは、それぞれの引数につき、標準モデルでビジービーバー関数の値になるものひとつを除いて証明可能。
>>838は充足という言葉のつかいかた間違えてた。
自然数のコーディングを決めて論理公理やらを前提として、ビジービーバー関数の定義文とされるものを充足する任意の標準モデルにおいて同じ関数を意味するように定義可能 >>795の最初の命題ってさ、計算不能関数なら機械的証明ができるとは限らないってそれ当然では? 2^n-1=1+2+2^2+2^3+2^4+2^5+・・・+2^(n-1)
n=2kのとき3で割り切れる
n=4kのとき5で割り切れる
n=3kのとき7で割り切れる
n=10kのとき11で割り切れる
n=12kのとき13で割り切れる
n=16kのとき17で割り切れる
n=a*kのとき
2^(a*k)-1は必ず(a+1)を因数にもつ
a=a1*a2のとき
2^(a1*a2*k)-1は必ず(a1+1)と(a2+1)を因数にもつ
2^(31)-1のとき
2^(31)-1は31+1=32=2^5を因数に持つはずだが
2^(n)-1は2で割り切れないので素数になる
2^(15)-1のとき
2^(15)-1は15+1=2^4を因数に持つはずだが
上記と同じ理由で割り切れないが
15=3*5なので7を因数にもつ 2^(n)-1
n=15kのとき
2^(n)-1は7と31と151を必ず因数にもつ
n=30kのとき
2^(30k)は必ず7と31と151と331を因数にもつ 1+2+2^2+2^3+2^4+2^5+2^6+2^7=(1+2+2^2+2^3)+2^4*(1+2+2^2+2^3)=(1+2)+2^2*(1+2)+2^4*(1+2)+2^6*(1+2)=(1+2^2+2^4+2^6)*(1+2)=((1+2^2)+2^4*(1+2^2))*(1+2)=(1+2^4)*(1+2)*(1+2^2)=17*3*5
2^(n*k)-1
2^(2*n*k)-1=1+2+・・・+2^(2*n*k-1)=1+2+・・・+2^(n*k-1)+2^(n*k)*(1+2+・・・+2^(n*k-1))
2^(2^(2^(n)-1)-1)-1=2^(127)-1は素数
2^(2^(2^(2^(n)-1)-1)-1)-1は素数 2^(2^(n)-1)-1
n=2^(2^(n)-1)-1
2^(2^(2^(2^(2^(2^(2^(2^(n)-1)-1)-1)-1)-1)-1)-1)-1
2^(2^(2^(2^(2^(2^(2^(2^(3)-1)-1)-1)-1)-1)-1)-1)-1は素数
2^(2^(2^(2^(2^(2^(2^(2^(5)-1)-1)-1)-1)-1)-1)-1)-1は素数
2^(2^(2^(2^(2^(2^(2^(2^(7)-1)-1)-1)-1)-1)-1)-1)-1は素数 定義 H(x)
x!*x!^x!
He(x)=
H(x)^H(x)
途中省略
Ts(x)=
Lv(x)!^Lv!
Og(x)=
Ts!^Ts(x)!
本編
Og(ラヨ数)
これ何桁くらい? 左から新しい数列、新しい配列表記のセパレータ、DANのセパレータ
(0,2)=(1:3)=(1,,2)
(0,2,2)=(1:4)=(1,,,2)
(0,2,2,2)=(1:5)=(1,,,,2)
こんな感じで数列や配列表記でもトリオ数列同等の強さを発揮しそう。
具体的な定義は考えて、どうぞ 結局、巨大数を生成する関数って、場合分けが多いほどビジービバーの状態数が多いのに対応するみたいな感じで、
基本的には場合分けが多いほど強くなりやすいでOK? ただ多いだけじゃ強くはならない。
強くするためのツボを押さえていかないと複雑なだけのサラダになる まじ卍関数
卍(x)=
例えば卍(4)=
卍(2)*卍(3)
卍(2)=2,卍(3)=2なので
2*2
4 下の関数はどれくらいの増加量ですか 教えて下さい
X : 0個以上の1以上の整数
Y : 0個以上の1以上の整数
a : 2以上の整数
b : 1以上の整数
c : 1以上の整数
d : 1以上の整数 のとき
@ b[1,X]c,d=b[X]c,d
A b[1]c,d=b→d→c
B b[X,a]1,c=b[X,(a−1)]c,b
C b[X,a,1,Y]c,d=b[X,(a−1),(b[X,(a−1),a,Y]c,d),Y]c,d
D b[X]c,a=b[X](c-1),(b[X](c-1),(b[X](c−1),・・・・(b[X](c−1),b)))
ただしDの式で右辺のbはa個
>>857
卍(x)=2^(フィボナッチ数列のx項目) 卍関数計算中... 1,2,2,4,8,32,256,8192,2097152,17179869184
36028797018963968 理屈が解ってればパッと詳細な答えが出る→答え合わせができる数式なら鍵と錠前になるけど……
巨大数って詳細な数値を最後の一桁まで出すようなもんじゃないからどうなんだろ 巨大基数を仮定すればNP問題が多項式で解けるとか無いの? >>861
ならば!!
「TMB」
TMB(x)=
TMB(x-1)^TMB(x-2) >>865
一応、ZFC+ω-huge cardinalの存在を仮定すれば、
Kunen's inconsistancy theoremと
principle of explosionより
NP問題が多項式時間で解けることを導ける。
まあ無意味だが。 >>210
SaidiやLepageに見放されてないんだな TMBの場合は...
1 2 2 4 16 65536 115792089237316195423570985008(続く)
(続き)687907853269984665640564039457584007913129639936
ぎゃあああああああああ ZFC + ω-huge cardinalを仮定したら
NP問題が多項式時間では解けない事を示せるよ というか >>874 が矛盾したらP=NPの証明完了 ■ このスレッドは過去ログ倉庫に格納されています