巨大数探索スレッド14
■ このスレッドは過去ログ倉庫に格納されています
>>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を認める派と認めない派にわかれる 任意のチューリングマシンが停止するか停止しないかが決まってるとか、そんな数学ではとらえきれない宇宙、なんだろう 宇宙って集合論のモデルだと思ってたんだけど、集合論のメタである計算機科学の概念なの？ 矢印使ってる時は定義をしっかり吟味して地道に具体的に計算してたのに 集合論に足を踏み入れた瞬間用語の定義やら具体例やらすっ飛ばしてサラダを量産するの 少し悲しい こ〜たえ
3↑↑4 （何兆桁もの数）256
わからん」わからん「
10^10^10 わくぁらん
65533 うぁくぁるぁん
3↑^3↑↑↑3 3 4↑^4↑↑↑↑4 4
以上ｄえす 集合論関連はTaranovsky先生もapproximatelyとお茶を濁してる。
チューリングマシンの停止性はそりゃ決まってるもんだけど形式的にはそうでもないというやつで、
前ビジービーバー関数がwell definedでないと言ってたのは今思うとそのへんのことを言ってたのだろうか？
いづれにせよビジービーバー関数ってそういうもんでもないんだけど 理解の範囲を越えてるから原始的な方法を語る
ってだけだろ
計算可能な手続きによる巨大数の定義は
具体的に計算アルゴリズムを示せることが唯一の取り柄
だから具体的な計算アルゴリズムの形で定義しないと
チューリングマシン語でも普通のコンピューター言語でもフローチャートでも何でも良いけど ZFは無矛盾かどうか決まってるけど分からないのと同じ？ 計算不可能関数は原理的に形式的な理解が不可能で、そういうところ人によってはけっこう気にするんだと思うわ
数学的プラトニズムを定義に認めない専門家もいることだし、とはいえこの件は数学的プラトニズムを数学的に明らかにしていないというのが問題なだけかもしらんが >>206
そんなところかね。無矛盾かどうかは最初から決まっている、しかし無から明らかにする方法が存在しない ビジービーバー関数ならまだしも、ラヨ関数あたりはどういうのを定義と認めるかがデリケートで、それにグーゴロジーを言語の追究と考えるのであれば計算可能か不可能かとかいうのは問題にならなくて、
たとえばラヨ関数のもととなっているFOSTよりも計算可能なCoCのほうがある意味言語としては強い
platnist universeを数学的に明らかにしないグーゴロジストの怠慢という批判はあるかもしれない 「言語」と言う言葉のつかいかたにすこし揺れがあって、ただ純粋に論理としての言語を指すのであればFOSTでビジービーバー関数を無条件で定義することはできないし、そういう解釈だとラヨ関数もビジービーバー関数と変わらない BEAFのレギオン配列と次元とレベルrの配列表記がよくわかりません
わかりやすく教えてください。 急増加関数が１つの自然数と１つの順序数からより大きな自然数を作るように
１つの順序数と１つの順序数を超えたなにかからより大きな順序数を作ることは
出来るのでしょうか 順序数を越えたなにかですか
まずはすべての順序数の存在を明らかにしたらその後に見えてくるかも？ 急増加関数は
非可算無限に到達出来ない
また(定義可能な)全ての急増加関数は
ある可算順序数に対する急増加関数で抑える事が出来る Hardyの急増加関数は
順序数を与えただけでは定義にならない >>210
結局
ある言語を定義して
その言語n文字で定義可能な最大の実数
をその言語のビジービーバー関数
とするわけだよね
今厳密に(細部まで含めて)定義出来てる言語って
チューリングマシン語とその派生以外に何がある？ n文字じゃなくて、
ゲーデル数にした時のn以下
の方が良いかな 記号としての言語ならそれこそ0と1だけでどんな関数も定義できてしまうし、ユニバースの問題だという見識は共有できてるという前提でいいんだろうか >>217
ビジービーバー関数だと「定義可能であること」の定義がいたちごっこになって数学的にはナンセンスになる。
「厳密に(細部まで含めて)」というのが定義文をどう解釈してもひとつの関数の定義になっていることをいうのであれば、
ビジービーバー関数を定義できる言語は存在しない、不完全性定理から導かれる 「定義可能な言語として」存在しないと言っとかないとだめだった 定義可能であることが厳密でないことはよく分かったが、そこにplatnist universeが出るのは謎
まずこのuniverseはグロタンディーク宇宙などの宇宙と同じでいいの？ >>219
言語は当然定義しないとダメだよ
◯◯言語による記述
ゲーデル数がn以下の物の中で実数の定義になってる物だけを選んで
その中の最大値をf(n)とする
n以下で実数の定義になってる物が1個もなければ
f(n)=0とでもしておく
あとは言語を定義するだけ ゲーデル数でなくても
n以下の記述が有限通りであれば
文字数でも何でもいい 正しい実数の定義になってるかどうか
をその◯◯言語で出来る必要はない
(◯◯言語の記述を◯◯言語で判別するのは無理だから当然) 関数自体(f)を◯◯言語で記述する必要も無い
定義が正しいかどうかは定義とは別の領域で行う
(証明が正しいことを証明するのと同じ) その定義かどうかの議論が計算不可能レベルだとどういう領域をとっても形式的に構成していくのが不可能で、
これがある種の厳密性の限界になる。
計算可能レベルでもZFCとかを無条件で信じること前提になってるだろといわれればその通りだが、
計算不可能レベルだと実際に構成された理論を前提とすることもかなわなくなる。 ただ単に記号の集まりと言うのであればFOSTによる記述の判別をFOSTで記述するのは可能で、
無矛盾性の強さやモデルの取り方の問題だったりする。
ラヨ関数で言うFOSTは何らかの宇宙を前提とした話だろう >>228
◯◯言語の特定の表現が実数が定義されてるかされてないか
なんて考える必要はない
言語自体の定義が正しくされてるかだけを
(考えたい人が)考えれば良い
>>229
ちゃんと定義された物だと
チューリングマシン語 チューリングマシン語
停止する表現のみ実数が定義され、
停止した時の1の個数をその実数の定義とする >>229
もっと簡単なのだと
0〜9までの数字を使って普通の10進数を表記する言語
0〜9 とべき乗の記号 ^ からなる言語
など
厳密に決める為には
「0文字の場合は実数定義にはなっていない」
「0^0 が現れた場合には実数定義にはなっていない」
など細部が明確になっている必要がある より一般的に
自然数全体をN
ある言語の表現全体の集合をL
Nから(Lの部分集合)への写像をa
ある集合S
LからS∪{undefinef}への写像b
{Sの部分集合}xNからNへの写像c
f(n) = c(b(a(n)), n)
が言語Lのビジービーバー関数 ■ このスレッドは過去ログ倉庫に格納されています
