巨大数探索スレッド14
■ このスレッドは過去ログ倉庫に格納されています
ハイパー原始について、なにか質問があったら言ってくださいー そんな感じ(言葉のチョイスは悪いけど)
数学に慣れてない人なら理解の流れとして計算不可能が後の方になりがち
つまり、数学に親しみのあるやつもっと来い ビジービーバー関数の理解は難しく無いと思うのですが たしかにその通り
でも例えば順序数を知らない人にビジービーバー関数のすごさが理解出来るのかって考えると難しい ビジービーバー関数の大きさを語るのに
順序数は関係ないよ 数学初心者
「そうなんだ」(帰納って巨大数的にどう重要なんだ？てか帰納ってなんだっけ) 確かに計算不可能は計算可能より大きいけどさ、1行でバシク行列超えたってのは凄いことだろ >>97サスカッチなどがwell definedでないという数論の専門家もいまして
あと計算不可能関数で定義された巨大数は具体的にどういう値かを計算機で決定することができないし、決定可能な分類として計算可能レベルを認めてもいいだろう。
・・・計算可能でも事実上決定不可能ではあるが
ほかには神託なくして計算不可能関数は定義できないとか 昔計算不可能レベルを認めると荒れてたのが逆になってるな well definedなこと と 強いシステムを作ることを天秤にかけて
どっちを優先することが巨大数論的に健全なの >>117
決定可能とは？
ビジービーバーに神託の要素があるか？ 計算可能
ある特定の言語で記述出来るって意味しか無いよ まぁ、計算可能にも不可能にも需要はあるから、いいではないか >>122
それな
計算可能にも不可能にも特徴がある
wktkしてきた さっさと計算可能と計算不可能でスレ分かれてほしいわ
何回この意味のない言い争いやってんだよ まあこのスレ事態もう要らないんですけどね
ここから新しい何かが生まれることなんてこの先ないんだから 人の興味が湧く方に意味のあるレスが付いていくだけの話。新ネタ書かずに批判しか書いてない奴、そっちの派閥がネタ不足っていう自己紹介乙。 Ψ(Ω＿ω)レベルの関数を考えたよ〜〜〜
でもまだうまく作動するかはわからない >>121
特定の言語で記述できるというより帰納的可算言語で記述できるが正しいかと >>120
任意の計算不可能関数fを計算機が扱える適当な形式言語で記述して、その関数に代入する十分大きいxを用意して、f(x)=yが成り立つとして、
fとxのコードが入力されてもf(x)=yが成り立つかどうかを判定するアルゴリズムが存在しない、という意味での決定不可能です。 すべてのチューリングマシンの停止性が自明となるような形式体系は存在しないので計算不可能レベルからはどうしても神託が絡む、
ということだとは思うが自信はない 人工知能に「無限」に関する問題を与えたらどういう反応を示すのでしょうか？ >>79の答え
1.矢印表記 3↑↑3=7625597484987 2↑↑4=65536 5↑↑2=3125
2.多角形表記 3[3]=27 10[3]=10000000000 2[4]=256
3.A(x,y) A(2,3)=9 A(4,0)=13 A(3,2)=29
4.永遠の努力 1+10+10↑↑2+ 10↑↑3+10↑↑4+ 10↑↑5+10↑↑6+ 10↑↑7+10↑↑8+ 10↑↑9
>>80の答え
A(x,y)=2↑^x−2(y+3)−3
(x↑^−2 y=y+1, x↑^−1 y=x+y, x↑^0 y=x*y )
答えはあっていましたか？それでは、جيد باي ビジービーバー関数のｎ状態２記号ってどういう意味か分かりやすく
教えてくれる方はいませんか 分かりやすく！？
そんなの俺たちに出来るわけないだろ… アドレスを保持するレジスタが1個
アドレスは全ての整数値になりうる
各アドレスに対して1bitのデータを保持する
プログラムはn個の命令からなる
各命令は以下のような動作をする
switch (*addr){
case 0:
5種類の動作のどれか
case 1:
5種類の動作のどれか
}
5種類の動作は以下
A : *addr++ = 0; goto 「n個の命令の1個」;
B : *addr++ = 1; goto 「n個の命令の1個」;
C : *addr-- = 0; goto 「n個の命令の1個」;
D : *addr-- = 1; goto 「n個の命令の1個」;
E : 動作停止 データとaddrは全て0の状態で
1個目の命令から動作を開始する >>136
質問の内容的にチューリングマシンの動作をイメージ出来てない前提でいいのかな…？
チューリングマシンの解説動画を探してみた。
http://www.nicovide○.jp/watch/s○27508501
が比較的わかりやすいと思う。シミュレータもあるし、それで動作させてみれば理解しやすいのでは？
(NG対策により○はoとmで) やっとNG抜けれた…。
以下、補足。
・ヘッドの内部状態の数が状態数。
ただし、wikiによれば、ビジービーバーでは停止状態はノーカウントにするっぽい。
つまり、n状態ビジービーバーは、停止状態を含めればn+1種類。
※シミュレータでは2つ停止状態を用意しているのでn+2種類
・テープに使用する文字の種類数が記号数。上記シミュレータでは空白も1つの文字と見なしてる
2記号ってのは、0か1しかテープにないってイメージ。
ビジービーバーでは、初期のテープが全箇所0って前提があったと思う。
人により0を空白と呼ぶ場合も別の記号と考える場合もあるっぽい。シミュレータでは別の記号としている。 void main(){
char *addr = 0;
command_1:
switch (*addr){
case 0: *addr-- = 1; goto command_2;
case 1: *addr++ = 1; goto command_3;
}
command_2:
switch (*addr){
case 0: return;
case 1: *addr-- = 0; goto command_1;
}
command_3:
switch (*addr){
case 0: *addr-- = 1; goto command_0;
case 1: *addr++ = 0; goto command_1;
}
} こんな感じのプログラムを内蔵した機械
上の例は3状態2記号の例
case の中身が機械によっていろいろと違う
このプログラムは
無限に動作し続けるか、いずれ停止する(returnに到達) するかのいずれかである。
3状態2記号の機械の中で停止するものだけを選ぶ
この中で、停止した時のデータ1の個数が最大の機械を選ぶ
最大の機械の停止時の1の個数がΣ(3)である。 n状態2記号の機械は (4n+4)^(2n) 個存在する
n状態2記号の機械の中で、
停止する機械は存在する
停止する機械は有限個である
よって、
nに対し、停止時の1の個数には最大値が存在する
これがΣ(n) goto を通った回数の最大値は最大シフト関数と呼ばれる ビジービーバー関数、最大シフト関数ともに、
定義は簡単なのに、非常に増大度の大きい関数である
初期状態のデータの値を与えることで、
さらに大きな関数になる。
たとえば、
Σ(n) の値となりうる番地だけ1、それ以外を0
という初期状態で始めたビジービーバーを考えた場合、
計算不可能次数が1個あがった、非常に大きな関数となる。 >>133計算可能であればfごとにアルゴリズムが存在し、そのアルゴリズムの複雑さに対応する帰納的公理化可能な理論が存在します。
>>134合ってはいますが、計算不可能関数も特定の言語で記述できますし。
1階述語論理による文をオラクルで与えられた適当な視点(集合論の何かしらの完全無矛盾拡大とか)から読み解くとか。 >>148
何が言いたいのか良くわからん
計算可能であればアルゴリズムが存在し...
ってほとんど定義そのまま
後半、
合っているなら「○○の方が正しい」も何も無いですね ビジービーバーが巨大数の出発点
チューリングマシン語n語で記述可能な数の最大値
更に巨大な数を定義するために
言語の表現力を上げていく
言語の表現力を上げていって矛盾スレスレ
が究極の巨大数を作れる言語
「n文字で定義出来る最大数」
に限りなく近づいていく 矛盾スレスレといってもそもそも無矛盾性の証明が不可能でf(a)=bやf(a)<bが本当は正しくても事実上証明できない曖昧さが残る Bonjour!今回はチェーン表記です。
定義
ルール1: a→b→c=a↑^c b (矢印表記を使用)
ルール2: a→…→b→1=a→…→b
ルール3: a→…→b→1→c=a→…→b
ルール4: a→…→b→(c+1)→(d+1)=a→…→b→(a→…→b→c→(d+1))→d
これもA(x,y)の様に、再帰で定義されています。
ちなみに3→3→3→3の時点でグラハム数を超えてしまいます。
次回はふぃっしゅ数v1とv2でお送りします。それでは、Bonne baye! >>151
無矛盾性の証明とか
計算可能であってもどうせ無理だから √(1+1/2^2-2*(1/2))=1/2 ←1の大きさと1/2の大きさのベクトルの向きががπだけ異なるベクトルの和の原点からの距離
√(1+1/2^2+1/3^2-2*(1/(2*3)+1/2+1/3))=0.799305254 i
√(1+1/2^2+1/3^2+1/5^2-2*(1/(2*5)+1/(3*5)+1/(2*3)+1/2+1/3+1/5))=1.15421931 i
√(1+1/2^2+1/3^2+1/5^2+1/7^2-2*(1/(7*2)+1/(7*3)+1/(7*5)+1/(2*5)+1/(3*5)+1/(2*3)+1/2+1/3+1/5+1/7))=1.37577849 i
2番目からは1と1/2と1/3のおおきさのベクトルが互いにπだけ異なった方向を指さなければならないため原点からの距離が実数にならない >>153
ZFCを基準にして証明することはできるしtwitterの企画なんかはそうしてた。ZFCを超えるものをどう扱うつもりなのかは分からんが >>150
なんの前提条件も無しに形式言語で計算不可能関数を定義するのは不可能で、真の算術なりplatnist universeなりの構成不可能な
ふわふわした概念を前提とする必要がある。
platnist universeがなんなのかは英語版の住民に聞いて ビジービーバー関数の定義はふわふわした概念を前提としてるか？ バシク行列システムは拡張したらどれくらい大きな数になるのかなあ >>158
バシク行列システム自体が強力すぎるので、生半可な拡張では大きくならないよね
海外勢は、Transfinite BMSと呼ばれる、バシク行列を拡張したものを作っていて、
(0)(1,1,1,,,)＝(0)(1[1]1)
こんなふうに圧縮するんだけど、画期的に大きくなったと言えるかどうか 計算可能かどうかを判別するチューリング機械では、例えば2記号の「2」とかがあるから、
数理論理学のメタとしてチューリング機械を導入するなら、結局ふわふわとした素朴自然数論を用いてると思うんだけど 特定の言語で記述可能と言う意味しかない
→いかなる言語でも記述不可能な巨大数を求めているっていう受け取り方がずれていた。
計算不可能レベルとしてはあながち間違いでもなかった。
関係ないけど最近googleがiPhoneをプレゼントしてくれるページに飛ばされがち KPにBIG FOOTのOrdに相当するものをくっつけて（L_{Ord(x)}がKP+「L_{Ord(y)}（ただしy<x）のクラスが存在する」のモデルになっている、みたいな）KP+「再帰的到達不能基数の存在」ぐらいの強さになるとか >>160
計算可能かどうかを判別するチューリング機械？？？？
何を言ってるのこの人 >>163
チャーチチューリングのテーゼから計算可能関数の定義にはあらゆるパターンがあってチューリング機械を使うものもある
巨大数のwikiもそうなってる いやだからチューリング機械で判別するのが計算可能関数の定義の一部なの
分からない人だねぇ チューリングマシン語で記述可能な関数が計算可能な関数
判別する能力とか関係ない どうでも良いけど
大きな実数の探索に結び付かないことは他でやってね გამარჯობა!今回はF1とF2です
F1.S変換と呼ばれる変換を以下で定義します。
S(m,f(x))=(g(m),g(x))
ただしg(x)は以下です。
B(0,x)=f(x)
B(x,0)=B(x-1,1)
B(自然数a,自然数b)=B(自然数a-1,B(自然数a,自然数b-1))
g(x)=B(x,x)
[2] SS変換と呼ばれる、(自然数, 関数, 変換) の3つ組から同様の3つ組への写像SSを定義します。
SS(m,f,S)=(S^f(m)(m,f),S^f(m))
f^何らかの関数(n)=何らかの関数(n)をm回重ねる
ここで右辺は((自然数, 関数), 変換)の形をしているが、これを(自然数, 関数, 変換)の3つ組と同一視します。。
3つ組 (m0,f0,S0) を m0=3, f0(x)=x+1, S0 はS変換とするとき、
SS^63(m0,f0,S0)
の第1成分をふぃっしゅ数バージョン1、第2成分をふぃっしゅ関数バージョン1とします。
F2は,,,もう明日やります。 >>157
任意のチューリングマシンの停止性が自明となるようにビジービーバー関数を形式的に定義できる言語が存在しない、
というような感じです。
(形式的に定義できないというのは読みとく側の問題でもあって、この言い方もあまり正しくはないが) F2は、やっぱ明日のE表記と同じ時にやります。あと1day待ってください。 ¡Hola!今回はE表記とF2です。
1.E表記
定義
E(b)a=b^a
E(c)a#b=c↑↑b↓a(↓..左から計算する矢印表記)
E(d)a#b#c = E(d)a#(E(d)a#(E(d)a#(E(d)#(...(c回...(E(d)a#b)...(c回)...))
E(f)a#b#c#d = E(f)a#b#(E(f)a#b#(E(f)a#b#(E(f)a#b#(...(E(f)a#b#c)...)) (d個のEa)
以下同様にして増えていきます。
2.F2
F2は、g(x)を定義するまではF1と同じですが、g(x)を定義したあと、S*と言う新しい変換を定義します。
(S∗f)(x)=(S^x f)(x)
SS変換の定義も異なっています。
SS(m,f,S)=((S^f(m)f)(m),(S^f(m))∗f,S^f(m))
そして、
3つ組 (m0,f0,S0) を m0=3, f0(x)=x+1, S0 はS変換とするとき、
SS^63(m0,f0,S0)
の第1成分をふぃっしゅ数バージョン2 F2、第2成分をふぃっしゅ関数バージョン2 F2(x) とします。
どうでしたか？次回はアッカーマン関数の応用編です。それでは、¡Buen baye! 十分強い矛盾した体系を取って来れば停止するチューリングマシンの非停止性を自明にすることはできる バシク行列システムのＢＭ２の説明が載っている所ってある? 안녕하세요!今回はアッカーマン関数の応用編です。
1.多変数アッカーマン
定義
X : 0個以上の0以上の整数
Y : 0個以上の0
a, b : 0以上の整数
A(Y,a)=a+1
A(X,b+1,0)=A(X,b,1)
A(X,b+1,a+1)=A(X,b,A(X,b+1,a))
A(X,b+1,0,Y,a)=A(X,b,a,Y,a)
2.F1の近似
F1≒A(1,0,1,63)
どうでしたか？次回は膨張、爆発、爆轟です。それでは、안녕! 巨大数を作った場合って、どこに投下したら精査してくれるの？ konnnitiha!今回は膨張、爆発、爆轟です。
1.a{b}c=a↑^b c
膨張は、
a{a{⋯{a}⋯}a}a(中心からb個のa)
となります。
爆発は、
a {{{1}}} b=a {{a {{a・・b times・・{{a}}・・・b times・a}} a}} a
となり、爆轟は
a{{{{{1}}}}}bとなります。
医科がでしたか？次回はF3を解説します。
それでは、sayounara! これがビジービーバー関数の定義だといってもその定義文をビジービーバー関数の定義として解読する環境を記述することができない。「ビジービーバー関数」という言葉でちゃんと同じ関数を共有できているかを形式的に保証するすべが存在しない。計算可能であれば存在する。
グーゴロジストなら気にしないのかもしれない。
しかしラヨ関数からの拡張って計算可能レベルに還元して考えるとあまり大したことないような、
それに定義する前の問題としてユニバースをどうするかとか >>174
停止性が自明となる→停止性の決定可能性が自明となる たまにこのスレで見るplatnist universeって何なの？
数学的プラトニズムっぽいのは分かるが qonnnitiwa!今回は今までのおさらいです。
1.チェーン 3→4→2=? 4→2→2=?
2.F1 S(2,x+2)=? S(4,x+3)=?
3.E# E10#2=? E(3)3#3#3=?
4.多変数アッカーマン A(0,0,4,1)=? A(0,1,2,0)=?
5.爆発 3{{1}}2=? 4{{1}}2=?
wakalimasuka?soredeha,sayounala! うーん 自分で考えた配列の評価に時間がかかるーーー むしろ簡単に評価できてしまうほうじゃないかね
評価が定まっていないのならラヨ関数以降の巨大数とかがそうだし まずplatnist universeを認める派と認めない派にわかれる 任意のチューリングマシンが停止するか停止しないかが決まってるとか、そんな数学ではとらえきれない宇宙、なんだろう 宇宙って集合論のモデルだと思ってたんだけど、集合論のメタである計算機科学の概念なの？ ■ このスレッドは過去ログ倉庫に格納されています
