巨大数探索スレッド13

1132人目の素数さん2017/12/08(金) 22:59:03.88ID:8DbvNjq1
大きな実数を探索するスレッドです。

前スレ
 http://rio2016.5ch.net/test/read.cgi/math/1484923121/
巨大数研究室
 http://www.geocities.co.jp/Technopolis/9946/
巨大数 (Wikipedia)
 http://ja.wikipedia.org/wiki/%E5%B7%A8%E5%A4%A7%E6%95%B0
ふぃっしゅっしゅ氏の巨大数論PDFと書籍
 http://gyafun.jp/ln/
たろう氏のまとめ
 http://gyafun.jp/ln/archive/7-571.txt
Dmytro Taranovsky の順序数表記
 http://web.mit.edu/dmytro/www/other/OrdinalNotation.htm
巨大数研究Wiki
 http://ja.googology.wikia.com/wiki/

784132人目の素数さん2018/05/21(月) 18:23:45.03ID:0ribCmLT
すみません
聞き方が悪かったですね

バシク行列やBEAFが最終的に出力するものは
実数?
帰納的順序数?
帰納的ではない可算順序数?
非可算順序数?

785132人目の素数さん2018/05/21(月) 20:40:08.78ID:4VRAtjed
なんでそこが疑問なんだ?
>>779の書き方が誤解を招くといいたいのか?

786132人目の素数さん2018/05/21(月) 22:03:27.86ID:2IbqZlSb
>>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はいらなかった。たびたびスマン

787132人目の素数さん2018/05/21(月) 22:13:32.07ID:PtHrX8aD
カントール標準系を総和の多重再帰で表現したらBEAFのもう一つの表現が出来そうなんだが何となくイマイチ

788132人目の素数さん2018/05/21(月) 22:39:18.40ID:2IbqZlSb
>>784
バシク行列もBEAFも自然数を出力します。
その関数部分の強さを表すのに帰納的順序数が使われます。(帰納的でなく再帰的と言いたい)

>>783
Hardyと順序数を使った物というのがよくわかりませんが、原始数列から拡張されているシステムを指すのであれば、とくにメリットがあるとは感じません。

>>781
BEAFはテトレーション空間の配列以降がいまひとつ活用できてません。うまいこと定義を修正してもpDANのアイディアには根本から及ばない感じです。

>>777
セパレータ(分離子と訳せばいい?)の強さのようなもので、順序数崩壊関数で大きな順序数を崩壊させるように使います。

1{1,,2}2 を崩壊させると、一例だけど

1{1{1,,2{1,,2}2,2}2}2

になったりするような。

789132人目の素数さん2018/05/21(月) 22:53:15.92ID:0ribCmLT
いまいち記述の意味がわからない

>>779 などに書いてあるのは
左辺は自然数、右辺は順序数

左辺が関数であれば、
その増加度をHardy階層の順序数で表している
というのならわかるのだが
左辺は自然数、となると右辺の順序数は何を表している?

その辺を一行だけでいいので省略しないで書いていただけると

790132人目の素数さん2018/05/21(月) 23:09:01.54ID:0ribCmLT
なんとなくわかってきた

{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}) 以下の全ての順序数を表現できる?

791132人目の素数さん2018/05/22(火) 12:26:22.53ID:vlHh6A2w
多変数最大シフト数関数
 強さ: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-記号チューリングマシンの中で最大のシフト回数

792132人目の素数さん2018/05/22(火) 13:13:42.72ID:rz/ll3MY
ゴミwww

793132人目の素数さん2018/05/22(火) 13:39:01.31ID:vlHh6A2w
多重リスト化してε^CK_1にすればゴミービーバーでなくなる?

794132人目の素数さん2018/05/22(火) 18:07:03.40ID:rz/ll3MY
ネタ切れだからって無理に書き込まなくて良いよ

795132人目の素数さん2018/05/22(火) 23:49:29.42ID:cVn+l2mj
自然数上の任意の計算不能関数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を偽とするモデル,...のいずれもありえる。

796132人目の素数さん2018/05/23(水) 00:52:22.97ID:4caPj6x/
∀n∃mP(n, m) ∧ ∀n∀x∀y((P(n, x) ∧ P(n, y)) ⇒ x = y)が証明できただけじゃwell definedとは言い切れないんじゃ。
異なる解釈で異なる関数を読み取ることができても成り立つから

797132人目の素数さん2018/05/23(水) 00:53:38.36ID:4caPj6x/
ビジービーバー関数がwell definedでないとは言わない

798132人目の素数さん2018/05/23(水) 01:51:53.68ID:zNN4cZlg
>>795
φ(0), φ(1), φ(2), ....,,, が全て個々に証明可能だとしても
∀n φ(n)が証明可能だとは限らない。
(例えばφ(n)を、nは矛盾の証明のゲーデル数ではない、
などとすればその例になる。)
∀n φ(n)を証明するには、φ(x)をxの値によらない
“一様な”方法で示してから全称量化しないといけない。
だから上に書いてある議論はおかしい。

busy beaver関数が計算可能じゃないのは、
実際には停止しない或るチューリングマシンTについて、
その非停止性が証明できないからだよ。
だからPeano算術なり何なりのベースの理論に
このTがm stepで停止する、という公理を付け加えると
ノンスタンダードな理論になる。
この理論のモデルの中では、Tが或る超準自然数mについて
m stepで停止するように見えている。

799132人目の素数さん2018/05/23(水) 07:17:50.67ID:4Fh4x0c6
証明可能とか以前に、ちゃんと定義しようよ

ふぃっしゅ数とかラヨ数とか
定義になってないものが定義として扱われて非常に違和感

800132人目の素数さん2018/05/23(水) 19:04:11.51ID:PutOeZzi
>>796確かに「>>796の思う」well definedの定義とは一致しないかもね。
>>798「だから」の前後が全然つながってない件

801132人目の素数さん2018/05/23(水) 19:14:05.61ID:PutOeZzi
>>795というかこれで証明のつもり?はしょりすぎだろ。

802132人目の素数さん2018/05/23(水) 19:32:19.05ID:zNN4cZlg
>>800
ごめん、完全性定理とか不完全性定理とか
算術の超準モデルの基本とかが
俺の脳内で勝手に一般常識みたいな扱いになってた

発表下手な人のパターン

803132人目の素数さん2018/05/23(水) 19:50:08.18ID:4caPj6x/
関数を一意に定義できてなくてもwell definedでいいの?

804132人目の素数さん2018/05/23(水) 19:57:48.60ID:5XOXl9ER
ダメ

805132人目の素数さん2018/05/23(水) 21:38:45.15ID:4caPj6x/
とりあえず1階述語論理で非停止性を証明することはできるよな。停止性を証明できたとしても超準ステップ数目で停止することを示している可能性を排除できない、
という意味であって

806132人目の素数さん2018/05/23(水) 21:47:59.06ID:4caPj6x/
ZFCが無矛盾だとしてもZFC+¬Con(ZFC)のモデルが存在するのと似てる。ω矛盾しておりすべからく超準モデルになる

807132人目の素数さん2018/05/23(水) 21:49:31.31ID:zNN4cZlg
もちろん出来るものもあるし、
本当は停止するのにその事を証明できないような
マシンもある

808132人目の素数さん2018/05/23(水) 21:57:45.98ID:4caPj6x/
逆では?

809132人目の素数さん2018/05/23(水) 22:56:27.80ID:amwAZ2U3
もはや哲学の域?

810132人目の素数さん2018/05/23(水) 23:09:01.76ID:zNN4cZlg
一階述語論理で非停止性を示すというのは、
どういう公理の下での話を想定してるの?
一階述語論理というのは¬とか⇒とか∀とかの
命題結合記号や量化記号を扱えるだけのシステムなので
A⇒Aとか(A∧B)⇒Aみたいなトートロジーを示せるだけで、
具体的な自然数やチューリング機械には
そもそも言及する事自体できないのだけど。

仮にZFCみたいな理論を公理に採用し
(て適切にチューリング機械の理論を解釈し)
たとしても、
実際に停止するマシンについては、
停止するまでのマシンの挙動を書き下すだけで
停止性の証明が出来るわけだから
任意の非停止マシンについて、非停止を示せるのなら、
停止問題が解ける事になって不合理でしょ。

811132人目の素数さん2018/05/23(水) 23:19:15.24ID:zNN4cZlg
>>808
ごめん、よく自分のレス見たら書き間違えてた、、

×本当は停止するのに
○本当は停止しないのに

812132人目の素数さん2018/05/24(木) 06:24:35.22ID:vEMyZpD8
停止するかしないかなんて神様がわかれば良いのだよ

813132人目の素数さん2018/05/24(木) 20:53:48.80ID:of0Asveb
可算無限集合の冪集合の濃度=連続体濃度がZFCのモデルによってアレフ1だったりアレフ2だったりするが、冪集合をとる操作がwell definedでないとか、一意ではないとは普通言わないな。

814132人目の素数さん2018/05/24(木) 21:14:53.84ID:l8QEZfSn
>>793
計算不可能レベルで再帰定義を取り入れるのがあまり歓迎されない。
引数nに応じてn-ビジービーバー関数をオラクルで呼び出すシステムを取り入れるだけくらいでいい

815132人目の素数さん2018/05/24(木) 21:17:20.63ID:pzFSY5oA
何か凄い初歩的で申し訳ないんだけど、
〜〜〜〜で決まる何とか函数がwell-definedである事を
言うためには、〜〜〜〜という記述が表わす対象が
一意に決まる事を言わないといけないんじゃないの?
〜〜〜〜が関数になっている事ではなくて。

816132人目の素数さん2018/05/24(木) 21:18:32.89ID:l8QEZfSn
モデルによって関数が異なる(ある標準的な自然数nについてf(n)の値が異なる)場合はwell definedとは普通言わないと思う

817132人目の素数さん2018/05/24(木) 21:22:13.60ID:l8QEZfSn
>>813の場合はアレフ1やアレフ2がwell definedでないということ

818132人目の素数さん2018/05/24(木) 21:25:12.49ID:l8QEZfSn
>>817言い方が悪かった。べき集合の濃度がwell definedでない

819132人目の素数さん2018/05/24(木) 22:08:46.58ID:pzFSY5oA
>>816
まあラヨ関数についてはそれで良い気がするけど、
だとすると、何かコーディング決めて
f(n)
:=m(自然数nのコードするチューリング機械が
mステップで停止する場合)
:=-1 (nのコードするチューリング機械が停止しない場合)
:=-2 (自然数nがチューリング機械をコードしない場合)
とすると、f(n)=-1という関係がwell-definedで
なくなり得る気がする

820132人目の素数さん2018/05/24(木) 22:16:17.95ID:l8QEZfSn
>>819
ZFCが無矛盾だとして(ZFCじゃなくてもいいけど)、nをZFCが矛盾するという証明列を見つけ出して停止するチューリングマシンのコードとすると、
超準モデルで考えるとf(n)は超準的自然数を返すが標準モデルで考えると-1を返す。

とか?

821132人目の素数さん2018/05/24(木) 22:26:45.97ID:c3neDLsf
そもそもモデルってなんなんだよ
3行で教えてくれ

822132人目の素数さん2018/05/24(木) 23:10:49.08ID:cwLgPhwH

はい俺の勝ち

823132人目の素数さん2018/05/25(金) 01:13:01.45ID:kGxSRdIp
定義文で関数を強くするよりも、定義文を上位の定義文で拡張すれば良いのでは
中の定義文を強化する言わばS定義文

824132人目の素数さん2018/05/25(金) 06:31:25.61ID:CsI1ck0q
>>820
だいたいそんな感じ。
そしてそれは標準的な入力に対しても起こり得る。

825132人目の素数さん2018/05/25(金) 09:56:35.48ID:gU+GX2s9
いや標準モデルではおこりえないんじゃ
知らんけど

826132人目の素数さん2018/05/25(金) 10:09:23.14ID:gU+GX2s9
>>795はビジービーバーがwell definedであることの説明になってないと思うし
関数であることや全域性を証明できてもモデルによって関数が変わるってつまりwell definedじゃないってことだしだからこそラヨ関数がwell definedでないと主張してたんじゃないかと

ビジービーバー関数もラヨ関数も任意のモデルで停止するとか命名文になるとかいうふうにすれば解決する、
というのであって

ラヨ関数は「任意の」という量化の範囲を公理のモデルにするか命名文のモデルにするかで2パターンに別れる

827132人目の素数さん2018/05/25(金) 10:38:10.91ID:oNqoenwT
む、むずかしい話でついてけない

828132人目の素数さん2018/05/25(金) 20:04:39.74ID:EKtLOPjB
とりあえず集合の濃度すらwell definedでないと思うなら、数学においてwell definedとはどんな意味の用語なのか調べたほうがいいんじゃないかな。
多分思ってる定義と世間一般での定義が違うから。

829132人目の素数さん2018/05/25(金) 20:09:51.85ID:dWd6vU9O
>>826はwell definedとはcomputableのことだと誤解してる
数学を知らぬ馬鹿の典型

830132人目の素数さん2018/05/25(金) 20:12:02.69ID:dWd6vU9O
>函数がwell-definedである事を 言うためには、
>(函数の)記述が表わす対象が 一意に決まる事を
>言わないといけないんじゃないの?

それは函数を定義する体系の強度に依存する
そういうことに無神経なのが、数学を知らぬ馬鹿

831132人目の素数さん2018/05/27(日) 00:59:04.29ID:Eccfjv+j
逆に>>830が考えるwell definedといえるものって例えば何?

832132人目の素数さん2018/05/27(日) 01:01:35.17ID:O4Prk3RW
集合の濃度がwell definedでないというんじゃなくて、べき集合の濃度というだけじゃどれほどの濃度かはwell definedじゃないという意見

833132人目の素数さん2018/05/27(日) 02:56:29.25ID:qjdaiiMu
モデルの取り方によって値が超準元になり得るというのは
ごく普通にあり得る現象で、普通に数学をしている場合は
それだけだwell definedでないとは言わないとは思う。


ただ、仮に標準的自然数の値のみを考えるとか
規約したとして、それで元々の問題においてきちんと
数を定義した事になるのかと言えば大変微妙なんだけど。
つまり、ある式が或る自然数を定義しているかどうかが
ZFC + 巨大基数公理みたいな死ぬほど強い公理系から
独立になってしまうので。

834132人目の素数さん2018/05/27(日) 03:00:55.15ID:qjdaiiMu
だから冪集合の濃度がwell definedでないという
言い方は普通しないよね。
2^aleph 0 = aleph αとした時に、αの値は
ZFCでは決定できない、とは言えるけど。

すごく単純な例で例えていうなら、
世の中にはアーベル群と非アーベル群があるから
群Gが可換かどうかはwell definedでない、
とか言ってるようなもの。

新着レスの表示
レスを投稿する