巨大数探索スレッド13
■ このスレッドは過去ログ倉庫に格納されています
>>730
つまり定義が完成してない
ってことになるな ラヨ数って大雑把に言って
「或る(集合論とか高階論理っぽい)体系X内で、N
(例えば1 googol)文字以下の形式的な論理式で
定義できる最大の数+1」という定義だと思うのだけど。
ところが、
式φ(x)が自然数mを一意的に定義しているかどうか
(そしてより一般的に、mがφ(x)を満たすかどうか)
というような事は、φがごく簡単な形をしている場合
以外は、Xの具体的な公理だけではなくて、
Xのuniverse(モデル)の取り方自体に依存して
大きく変わってしまう事が知られている(※)から、
Xの公理を決めてもこれだけだと全然
well-definedな定義にならない。
という事を先日、集合論専門の先生が
コメントしてたりするけど、
まあコメントを読んだほぼ全員が理解してないよねw
“satisfaction is not absolute”というarXivの論文が
(※)の分かりやすい解説なんだけど、いくら
分かりやすいとは言え、基礎論の教科書を一冊通読して
完全性定理と不完全性定理の証明を最初から最後まで
フォローしました、くらいじゃ全然この論文を読める
レベルには達しないから、まあ素人にも分かるように
専門家が反論するというのも困難な話。
中学生に今年の東大入試の数学の問題の模範解答を
解説するのが難しいようなのもので。
だから数理論理ってなかなか怖い分野で、
数学や哲学の専門の有名な先生が堂々と
トンデモみたいな事を書いたり言ったりしてて、
しかもそれがデタラメだという事が、
一部の詳しい人にしか分からなかったりする。 誰か Rayo number is not defined っていう論文を書いて arxiv にアップしてよ
実際に、Wikipedia ではすでに8ヶ国語の記事になっているくらい広まってるわけだし、
こんな掲示板に書いたって誰も信じないから、きちんと専門家に書いて欲しい
査読誌だと通るかどうかわからないけど、arxiv なら出せるでしょ いやwell definedじゃない派はそれなりにいると思うよ 定義されていないというより、
メタレベルの自然数nと、体系のモデルMに依存して
決まって、Mをちょっと変えると
全然違った値になるという事。
だから相当好意的に解釈するなら、
well definedでないとまでは言えないんだよね Rayo number is not a unique number でもなんでもいいよ
そういう「引用可能な文献」があれば、Wikipedia の記事にも直接その論文を引用できる 個人的にuniverseの取り方の部分は、複数の異なるモデルを含むほど大きなuniverseを取って解決出来るんじゃないかと思ってるけど確信はない universeの取り方のくだりでwell definedでないのを主張するのは例を示して公表するのが一番手っ取り早くて効果的だな。言うほど簡単でもないだろうが 1階の定義文なら公理だけに注目すればいいのでは。
2階以降が絡んでくる定義文なら公理だけでは解決できないというのはおk というかなんで「みんなラヨ関数がwell definedだと信じてる」ことになってるんだ?
だいたいみんなお茶を濁すかんじで、well definedだと断定している人っていたっけ 未完成って指摘した時反対されたから
てっきりみんなwell-definedと思ってるのかと思ったが 掲示板というのは、そのときそのときに見た人が糧に書き込んでいるわけで、
いる人もコロコロ変わる。ある時に誰かが書き込んだことは、その匿名の誰かの
意見という以上の意味はない。 Googology wiki でも、専門家が定義したんだから間違いないという盲信派と
積極的には認めたくないけど認める立場もあるのかなという懐疑派が多くて、
積極派はビッグフット作った人くらいじゃないかな
サスカッチ作った人は、懐疑派 ビジービーバー関数はwell definedでいいの? >>750
専門家がwell definedっていうんだから間違いない。 busy beaverは50年以上前から明確に
定義されてる函数で、最初のいくつかの値については
実際に値が計算されている。
定式化の曖昧さとかも無いし、標準的な
(=超準自然数でない)nでの函数の値が
モデルの取り方によって変わり得るということもない。 多変数ビジービーバー関数の定義
f: 任意の関数
x,n: 0以上の整数
N(f, x, 0) = x
N{f, x, n+1} = f( N{f, x, n} )
BB: ビジービーバー関数
x,n,a: 0以上の整数
Y: 0個以上の0以上の整数
a#n: n個のa
B[](x) = N{BB, x, BB(x)}
B[0#(n+1)](x) = B[x#n](x)
B[Y, a+1](x) = N{B[Y, a], x, B[Y, a](x)}
B[Y, a+1, 0#(n+1)](x) = B[Y, a, x#(n+1)](x) ビジービーバー関数に頼った再帰とか
虎の威を借る狐じゃないんだから まあ、ゴミは置いといてw
ビジービーバー関数がf_ω_1^CK(n)であるとして
f_ω_2^CK(n)に相当する関数はどんなものがあるの? 初期テープ状態を
Σ(1), Σ(2), .... の位置を1
他は0
とした時のビジービーバー関数 チューリングマシンが既知とすれば
これが一番簡単な定義
これだけで特に曖昧な点も無い おっとしまった
ビジービーバー関数Σだと無限になっちゃう
最大シフト数関数Sにしよう 初期状態も
S(1), S(2), ... の位置が1
の方が良いね 初期テープ状態を
S(1), S(2), .... の位置を1
他は0
とした時の最大シフト数関数をS^2(x)と定義した時
初期テープ状態を
S^2(1), S^2(2), .... の位置を1
他は0
とした時の最大シフト数関数の大きさは、f_ω_3^CK(n)
という認識であってる? >>758 >>761
この定義って、自然数のコード化にオラクルをつかっただけで強さはビジービーバーから変わってない、
ということは考えられない? なるほど、すると
初期テープ状態を
S(1), S^2(2), S^3(3), S^4(4), S^5(5) .... の位置を1
他は0
とした時の最大シフト数関数の大きさは、f_ω_ω^CK(n)
となるといいなあ そうやってHardyのような階層が作れる
でも次は
ω_(ω_1^CK)^CK を越えないとおもしろく無い 言うほど述語論理とか順序数について デタラメな事言い散らされてる? 述語論理とか順序数はしらないけどビジービーバーがwell definedじゃないとかはデタラメだろう。 >>770
スレもペースダウン書いたらいいんじゃないか。 なにが結論なのかは分からんが、
今のところDANまでがwell defined
そのDANの強さがバシク行列で(0,0,0)(1,1,1)(2,2,1)(3,0,0)でZ_2の証明論的順序数に相当する
らしい 結論だけ
{1,,n} が Ω_{n-1}
{1,,1{1,,1,,2}2} がψ_I(0) で {1,,1,,2} が I みたいな >>775
非加算の順序数が書いてあるようだが
結論の解説を ε_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 + 巨大基数公理みたいな死ぬほど強い公理系から
独立になってしまうので。 ■ このスレッドは過去ログ倉庫に格納されています