巨大数探索スレッド13
前スレ
http://rio2016.2ch.sc/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/
http://ja.googology.wikia.com/wiki/%E5%B7%A8%E5%A4%A7%E6%95%B0%E6%8E%A2%E7%B4%A2%E3%82%B9%E3%83%AC%E3%83%83%E3%83%89
寿司 虚空編 -Sushi Kokuu Hen-
https://comic.pixiv.net/works/1505
文明のレベルはビジービーバー関数の値をどこまで求められるかで測られる。
現在の人類の文明レベルは4
絶大なコンピュターパワーでビジービーバー関数の計算にチャレンジしてほしい
いっそ社畜関数って名前にしてしまえばもっと共感を呼ぶ
指数関数レベルの増え方とは次元が違う・・・と思ったけどほんとにそうだろうだろうか？
これは本当に最後まで走らせる必要があるわけではない、
どこまで計算効率を上げられるか
停止しないプログラムは停止しないという判定をしなければならない。
限定的に停止性を判定するアルゴリズムは存在するものの、それをどこまで簡単にできるか？
またそのプログラムを開発するプログラムはもっと複雑になるのではないか？
停止性を判定するプログラムはオラクルで与えられてもいい、つまり適当に作ったプログラムが
たまたまそうなっていたとしてもいい、ではそれがほんとうに停止性を判定するプログラムであると
判定するプログラムは？
停止性を判定するプログラムであると判定するプログラムであると判定するプログラムは？
これもうわかんねえな
普通にゲーデルの不完全性定理を停止問題として言い換えられるのぐらい知ってて言ってるよね？。
Googleが頑張ればそのうちなんとか、とか思わないでもない
グラハム数だって計算しようなんてヤツはいない
たとえば4状態のプログラムは有限個しか存在しないので、究極最初からプログラムの中に
それぞれの入力されたプログラムに対する答えを用意しとけば4状態の停止性を判定する
プログラムとなります。
と書いて思ったけどこんなのでもアルゴリズムと言っていいのか？ プログラムとは言えるけど
逆も然りだが、こちらからはけっこう難解
優勝マシンを決定すること
その一般的なアルゴリズムはないけど、小さいnに対しては決定できても
おかしくはない
それを追求しても巨大数探索にはならんぞ
ω矛盾の定義がおかしい。∃n∈(自然数)(Q(n))が証明可能なのに
Q(0),Q(1),Q(2),...がいずれも証明不能であることをω矛盾の定義といってたが、
これだとペアノ算術に例えば定数記号aを加えただけの拡張でも、
a = a から ∃n (a = n)が導出できる一方で、a = 0,a = 1,a = 2,... のいずれも証明不能で、
ω矛盾になる。しかし、これにa = 0という仮定を加えても無矛盾だから、
超準モデルになるとは限らない。
間違いの源はおそらく日本語版wikipediaだ。
"ω矛盾とは、自然数 n によって定まる論理式 Q(n) が存在して、次を満たすことをいう。
Q(0), Q(1), Q(2), …が全て証明可能であるが、「∃n： ¬Q(n) 」も証明可能である"
この記述は正しい。問題があるのはその下の、
"公理系が無矛盾であれば、対偶を取る事により、ω矛盾の概念が次と同値である事を示せる：
「∃n： Q(n) 」が証明可能であるが、Q(0), Q(1), Q(2), … のいずれも証明可能ではない。"
というところだ。最初の記述は「Q(0),Q(1),Q(2),...が証明可能で、かつ∃n(¬Q(n))も証明可能」
と言い換えられる。すると、実はAならばBの形になってないから、そもそも"対偶を取る"のは変だ。
英語版wikipediaには下の記述に該当する文は無い。
同値でないことも簡単に確認できる。ペアノ算術に定数記号aを加えただけの拡張は、
∃n(a = n)が証明可能で、a = 0, a = 1, ...が証明不能なことから下の記述を満たすが、
∃n(¬(a ≠ n))が証明可能な一方、a ≠ 0, a ≠ 1, ...は証明不能だから、上の記述を満たさない。
よって2つの記述は同値でない。
だから、前スレのあの証明では、「ビジービーバー関数の出力が超準的自然数になる」ことは
証明できていない、と言える。
あー、すっきりした
BB(x)をビジービーバー関数として、
「十分大きな自然数Mについて、0 < BB(M), 1 < BB(M), 2 < BB(M), ...が証明可能」
は証明できてないけど、もっと弱い主張である※ならば簡単に証明できる。
(∀n(n < BB(M))と、0 < BB(M), 1 < BB(M), ...は異なる。∀n (n < BB(M))からは、
例えばBB(M) + 1 < BB(M) を導出できるので明らかに矛盾)
※: 任意の無矛盾かつ帰納的公理化可能な公理について、ある自然数Mが存在して、
任意のn ∈ {0,1,2,...}について公理に n < BB(M) という式を加えてもなお無矛盾
やや分かりにくいけど、公理に0 < BB(M)とか1 < BB(M)とか 2 < BB(M)をいくら加えても
そこから矛盾が導出できない、ということ。ビジービーバー関数を扱える公理じゃないと
いけないので、多分自然数論を含むだろう。
導出できるような n ∈ {0,1,2,...}が存在すると仮定する。
公理が帰納的公理化可能なので、以下のような計算機械を構成すれば、必ず停止する
k = 0 とする
親プロセス:
(1).子プロセスに k < BB(M)を与えて起動する
(2).子プロセスが1つでも停止したら(3)へ
そうでなければ k を 1 増やして(1)へ戻る
子プロセス:
k < BB(M)が与えられたら公理 + (k < BB(M))から
矛盾の導出を試みて、矛盾を導出したらkを出力して停止
また、親プロセスが停止したら停止
すべてのプロセスは並行して行われる
この計算機械の出力する値を N とすると、N < BB(M)から矛盾を導出したので
N ≧ BB(M)を導出でき、状態数M以下のチューリングマシンをエミュレートして
N個を超える1を出力した時点でそのチューリングマシンは停止しないと判定できる。
どんなに大きな自然数Mに対してもこのことが言えるので、
任意の停止性問題を解ける計算機械が構成できることになり矛盾する。
よって背理法より※が示された。
例えば、いかに大きなn∈{0,1,2,...}についてもn < BB(M)の仮定と矛盾しないということは
ある程度大きなMについてBB(M)に意味のある上限を導出できないことを意味する。
上限 m∈{0,1,2,...} が導出できるなら、m < BB(M)の仮定を加えると矛盾し、※に反するから。
(ここでいう意味のない上限とは、BB(M) < BB(M) + 1など)
ある程度大きなというのがどれくらいかは公理によるが、例えばZFCで100とすると
BB(100)の上限がふぃっしゅ数ver6ぐらい、とか、H(ψ(Ω_ω))である、といった
何かしら計算可能なもので表せると証明されることはありえない、ということになる。
あとは、"公理が無矛盾 ⇒ 公理 + (n < BB(M)) が無矛盾"は示した通りだが
逆は明らかなので公理と公理 + (n < BB(M))は無矛盾性同値でもある。
なんだか、まるでBB(M)は連続体濃度みたいな感じがする。
連続体濃度cも、ZFC + (アレフ1 < c) とか ZFC + (アレフ2 < c),...にしたって無矛盾だし、
cは存在するし一定の濃度でもあるはずだけど、可算無限との間にいくつの濃度の異なる集合が
あるのか決まらない、といったような。
何をもって一意に定まるとするのかは、もはや哲学の問題だね。
ちゃんと大きさが見積もれる
と言っていると勘違いされた可能性はどうだろう
「どんなに大きな自然数Mに対しても、n < BB(M)を仮定すると矛盾が
導出できるような n ∈ {0,1,2,...}が存在する」
としたら、「1をn個出力するまでチューリングマシンを走らせる」とするだけで
停止性問題が解決してしまうので、そういうnが存在しないということが
停止性問題と同値であることは自明
小さな数しか作れないものは否定されてもしょうがない
ってどのくらい大きいの？
「無限」じゃないですかね
元の無限とは異なるんだろうけど
例えば、ｕ×０＝１という関係が成り立つｕを仮定して、これをあたかも虚数単位のようにして数を拡張すること、
具体的には、実数集合Ｒに対して、このｕを使って集合Ｕ＝{ａ＋ｂｕ|ａ、ｂ∈Ｒ}を定義することができるが、このような集合Ｕに、果たして数学的な意義はあるのか
それともまったく無意味なのか
こんなことを思い付いて研究してる数学者が、じつは既に居るんじゃないかって気がしてるんですが、その辺りどうなんでしょうか？
だね
とりあえず、ある程度までは自力で考えてみよう
でも
(1/0)*0
は1じゃなく0/0になっちゃうが
という哲学の問題なのかな。
いったんここでは自然数論のモデルに属しうるものはすべて自然数と呼ぶことに
して、以下の4つに分類しよう。特に断りがない場合、証明可能とは古典論理の
もとで証明可能であることを意味する。
(1)存在を直観主義論理のもとでも証明可能な自然数
例: ふぃっしゅ数ver6など、計算可能な手段で求められるもの
(2)存在を証明可能だが、直観主義論理のもとでは証明不能な自然数
例: ある程度大きな入力に対するビジービーバー関数やラヨ関数、
その他の計算不能関数の出力？
(2)の数は、さっきの※みたいな、任意のn∈{0,1,2,...}についてnより大きい
としても無矛盾、といったやや奇妙な性質をもつようになると思われる。
続く
おそらく存在が証明不能であるが、無矛盾性は強くしない自然数
おそらく、としたのは自然数論が矛盾していれば何でも証明可能であるため。
例: 「自然数論の矛盾の導出を試みて、導出したら停止する計算機械」
が停止するまでにかかるステップ数
自然数論 + (自然数論は矛盾)という公理を採用すれば停止することを証明可能で、
自然数論が無矛盾ならば(自然数論は無矛盾)は導出できないため、
自然数論が無矛盾ならば、自然数論 + (自然数論は矛盾)もまた無矛盾
よって無矛盾性は強くなっていない。
(4)存在を仮定すると、ω矛盾になるうえ、無矛盾性も強くなるが、
矛盾はしないような自然数
集合論では、大きすぎて存在を仮定すると無矛盾性が強くなるような
濃度のことを巨大基数と呼ぶのだった。いわば、(4)は自然数論版の
巨大基数である。ただしこれについての研究はほとんど無いから、
具体例を挙げるのは難しい。
(3),(4)に属する自然数は超準数で、したがって(1),(2)に属するどの自然数よりも大きい。
(1),(2)は存在を証明できる自然数で、(3),(4)は存在しないとは証明できない自然数である。
(4)に属する自然数はおそらく(3)に属する自然数よりも大きい。
実数1は乗法の単位元なので、1 + 0 = 1と分配法則から
u = u * 1 = u * (1 + 0) = u * 1 + u * 0 = u + 1
よって u = u + 1 両辺からuを引いて 0 = 1 実数の0と1は等しくないので矛盾
だからこのような u は、(1)から(4)のどれにも属さない、
存在を仮定すると矛盾が導ける数、ということになる。
>>39
さすがに0の逆数っていうのは先述の通り矛盾するからないけど、
どんな実数よりも大きい超実数という数の存在を仮定して色々する
超準解析っていうのがあるよ。
通常の算術が成り立たなくなることは理解しました。ありがとうございます。
スレチってこともあるのであまり深くは掘り下げないことにします。
そういえばu=u+1って式はuが可算集合濃度だと成立する式ですね。この場合は辺々uを引く操作に意味がないわけですが。
ビジービーバー関数が存在することに疑問の余地がある？
ビジービーバー関数の何が証明不可能だと言ってる？
Σ(9^9^9)が明確に定義されていて存在することは明らかだよね？
到達不可能基数のような、巨大基数を仮定すると定義できる巨大自然数
みたいなのがあるの？
関数であればそういう物もあるような気がするけど、
単なる１個の自然数にそういうのがある？
自然数に計算可能も計算不可能も無いよね？
不可能レベルだけでそんなに話題があるだろうか？ と思って前スレみてみたらそこそこあるな
"ω矛盾とは、自然数 n によって定まる論理式 Q(n) が存在して、次を満たすことをいう。
Q(0), Q(1), Q(2), …が全て証明可能であるが、「∃n： ¬Q(n) 」も証明可能である"
これは正しい
"公理系が無矛盾であれば、対偶を取る事により、ω矛盾の概念が次と同値である事を示せる：
「∃n： Q(n) 」が証明可能であるが、Q(0), Q(1), Q(2), … のいずれも証明可能ではない。"
これは確かにおかしいと思う、Q(0), Q(1), Q(2), … のいずれも証明可能ではないというのは統語論的に
決定できないと言うだけで、Q(0), Q(1), Q(2), … のいずれも反証可能ということではないので
程度なんだから、話題なんてごった煮でよくて、巨大数に関することは基本的になんでもあり
A に可算無限個の式を加えた以下のような公理
A + (0 < BB(M)) + (1 < BB(M)) + (2 < BB(M)) + ...
を A* として、コンパクト性定理より A が無矛盾なら A* も無矛盾
A から ∃n (n = BB(M)) を証明可能とすると、 A のモデルはすべて
BB(M)に該当する数を含む。 一方で A* のモデルではBB(M)は必ず
超準数である。A* が A を含むから、A* のモデルは A のモデルでもあり、
したがって採用する A のモデルによってはBB(M)は超準数になる。
さらに A がω無矛盾であるとすると、 A のモデルには標準モデルもあるため、
採用する A のモデルによってはBB(M)は標準数∈{0,1,2,...}になる。
したがってBB(M)の値はモデルの選び方に依存して変わる。
f が自然数上の計算可能関数とすると、n∈{0,1,2,...}について
0 = f(n), 1 = f(n), 2 = f(n), ...のうちのいずれかは証明可能である。
証明可能な式はどんなモデルを採用しても真なので、標準数を入力したときの
計算可能関数の出力する値はモデルの選び方に依存しない。
当然、0 = BB(M), 1 = BB(M), 2 = BB(M), ...のうちのいずれも証明不能である。
これは、任意の n∈{0,1,2,...} について n < BB(M) としても無矛盾である
ことによる。(n < BB(M) ならば n ≠ BB(M)である)
さっきは暗黙的に標準モデルで考えたために(2)の具体例が(3)の具体例
よりも小さいって言ったけど、超準モデルの中にあるBB(M)だったら
(3)の具体例を超えることも十分に考えられるな。
○○を満たす最小
みたいなのがあるわけで
整数だと
nが○○を満たせばn-1も満たすから
そういう形で大きな数を定義するのは無理では？
公理系によってBBの値は変わらんよ
公理系で証明可能だろうが不可能だろうが
BBの値に影響無い
単に選んだ公理系に証明の能力が無いだけ
その大きさをまともに扱えない公理系を使うのが間違い
幼稚園児がBB(4)=14の矛盾を導けないからといって
BB(4)=14と教えれば幼稚園児にとってはBB(4)=14である
と言ってるようなもの
公理によって値を返すかどうか証明不可能なものがあったと思うけど
深く勉強してみたいものだ。
公理系の強さは全順序じゃないけど
少なくともZFCにおいては、BB(4) = 13 が証明されているから、
ZFCのもとで 4 は※をみたすほど大きな数ではない。
無数にある無矛盾な公理系のうちどれを採用すべきかは数学の範囲内
じゃ答えられないし、ある公理がもつ無数のモデルのうちのどのモデル
を採用すべきかも数学の範囲内じゃ答えられない。
しかも、ビジービーバー関数の出力をすべて決定できる無矛盾な公理は必ず
帰納的公理化不能になるから、そんな公理の採用を強制されても神様にしか
扱いきれない。
数学の範囲内で答えられないなら哲学の出番になるけど、俺は哲学的議論
なんてしたくない。決着がつくことはほとんどありえないからだ。
俺はそんな哲学的議論をするより、あくまで数学の範囲内で、
そして人間が扱える公理の範囲内で、考察対象がもつ性質について
述べる方がずっと面白いと思う。
どの公理系を選ぶかなんて考える必要は無い
その辺はBB(4)となんら変わらない
実際に値を求める必要は全くなくて、
大小を比較する手段があれば十分
定義できたとみなしたときに、それを「チューリングジャンプ」とか「神託機械によって
計算された」と表現するので、計算可能性理論の領域に入ってくる。
>「十分大きな自然数Mについて、0 < BB(M), 1 < BB(M), 2 < BB(M), ...が証明可能」
>は証明できてないけど、もっと弱い主張である※ならば簡単に証明できる。
これがおかしい。ビジービーバー関数はFOSTで記述可能、
よって1階述語論理の完全性により、任意の自然数ｎにつきあるaがただひとつ存在し、BB(n)=aを
証明可能
定義することもできる、というかそういう定義だよな？
(sin(1/2)+sin(1/3)+sin(1/5)+sin(1/7)+sin(1/11)+sin(1/13)+・・・+sin(1/P(n)))^2+(1+cos(1/2)+cos(1/3)+cos(1/5)+cos(1/7)+cos(1/11)+cos(1/13)+・・・+cos(1/P(n)))^2≒(n+1)^2
>>69 公理とモデルごっちゃにしてない？
>>73 >>25は別に∃a(BB(n)=a)が証明不能とは言ってない。
BB(n)=0,BB(n)=1,...の内のいずれも証明不能なのは>>57の通り>>25の※から導けるけど。
ビジービーバー関数がちゃんと定義できてないなんて言ってるのは>>76だけ
∃a(BB(n)=a)ではなくBB(n)=aが証明可能、つまりBB(n)=0,BB(n)=1,...の内のいずかが証明可能
であり※は誤り、という主張です
>N個を超える1を出力した時点でそのチューリングマシンは停止しないと判定できる。
N個を超える1を出力した後にその1を消して停止することも考えられるのではないでしょうか？
これはこちらの勘違いでした、スマン
BB(n) = 0, BB(n) = 1, ...のいずれかが(帰納的公理化可能な公理から)証明可能なら、
>>26と似たような計算機械、すなわち
BB(n) = 0の証明を試みる子プロセス、BB(n) = 1の証明を試みる子プロセス、...
を次々生成する親プロセスを作り、子プロセスが一個でも証明完了すれば
得られたBB(n)を出力して全プロセスを終了、とすれば子プロセスの1つは証明完了
することは確実なので、BB(n)を計算できる機械が作れ、BB(n)の計算不能性と矛盾
優勝者よりも多くの1を書きながらそれを消して停止するマシンの存在は
確かにありそうで、その点で>>26には問題があるけど、
「N個を超える」のところは「N*2個」とか「N^2個」、はたまた「2^N個」
「Ackをアッカーマン関数としてAck(N, N)個」と置き換えても停止性問題を
解ける機械が作れるという結論に変わりなく、わざわざAck(N, N)個以上書いた1を
N個未満になるまで消してから停止するマシンがあるのに優勝マシンにはたったの
N個しかテープに1が無い、っていうのは(証明はしてないが)考えにくい。
だから結論は疑っていない。
例えば0を読み取ったら状態も文字も変えずただ右にシフトするだけだったら、
空のテープをずっと右に行くだけで停止しないのに1の数は0個のままだから
停止しないと判定されることもない。
>>26 はまずいな... ビジービーバー関数じゃなくて最大ステップ数関数に
譲歩したほうがより安全か。
どこまで計算しても「計算がいずれは終了するのか永遠に終了しないのかを判定する
一般的アルゴリズムは存在しない」ことが停止性問題。最大値を確実に見積もれたら、
その最大値まで計算すれば判定ができてしまうので停止性問題が解決してしまう。
つまり、>>26の仮定がおかしいということ。
>>35では>>84の例で出した1を出力しないのに停止しないマシンには対処できてない。
いましがた、詳細は省くが、任意のn状態数チューリングマシンに対して、
少なくとも21n状態数チューリングマシンなら1ステップごとに1の数が少なくとも1つは
増えていく、つまりステップ数を数えながら動くマシンを作れることが分かった。
これより、最大ステップ数関数S(n)
= "n状態数チューリングマシンが停止するまでにかかるステップ数の最大値+1"
とすれば、 BB(n) ≦ S(n) ≦ BB(21n) となる。
あとは>>26を改造して n ≧ S(M)が導けたときに n ステップまで動かせば停止性問題解消、
とすれば、あるMが存在し 0 < BB(21M), 1 < BB(21M), ...を加えても無矛盾と言える
ので、∀n (BB(n) < BB(n+1))から、結局は※と同じことを導出できるな。
超準モデルを否定できるのとのつながりが分からない。
子プロセスの「矛盾を導出する」のはチューリングマシンと同じ能力の計算機械で出来るの？
特定のチューリングマシンの停止性を判定できても矛盾はない・・・よな
超準モデルは必ず無限下降列をもってたと思う
それぞれに存在するだけなら停止性問題に触れない
なるほど。「詳細は省くが」のところが、けっこうすごいことやったのでは？
一階述語論理の健全性と完全性より証明可能⇔恒真
帰納的公理化可能な公理から証明可能な式は枚挙可能
よって証明可能な式を枚挙していれば必ず恒真な式は証明される
>>89
ZFCの無限公理が存在を保証する集合をNとして、ZFCが無矛盾なら、
ZFCに定数記号 v を加え、ZFCに v ∈ N という式を加えても無矛盾
{} ∈ v, {{}} ∈ v, {{}, {{}}} ∈ v , ...の式を有限個加えても無矛盾
よってコンパクト性定理より、
ZFC + (v ∈ N) + ({} ∈ v) + ({{}} ∈ v) + ({{}, {{}}} ∈ v) + ...もまた無矛盾
これをZFC*とすれば、ZFC*のモデルはZFCのモデルでもあるが、超準モデルである。
ZFC*は正則性公理を含むので、ZFC*のモデルの中の集合は∈の無限降下列を持たない。
よって無限降下列が有無を根拠に超準モデルを排除できる訳ではない。
この事実をあえて解釈するなら、超準モデルの中では超準数は有限にしか見えない、
だから自分が超準モデルの中にいるのか標準モデルの中にいるのか分からない、
といったところか。
自然数Mを入力として与えれば、論理式 n < BB(M)の構成自体は計算可能な手段
で出来るから、 >>26の計算機械は任意のMを入力にとることができる。
だから任意のチューリングマシンの停止性を判定できる一つの計算機械になって矛盾を導ける。
>>91
そんなに気になるか〜。仕方がない。省いた部分を書いてあげる。
テープを 3k, 3k + 1, 3k + 2 番目のセルの3つに分割して、
3k 番目のセルはエミュレート用に、3k + 1, 3k + 2 番目のセルはステップ数の
カウントと制御用に使う。
n状態数マシンのエミュレートを行い、エミュレータが
1ステップ進むたびそこのセルの1つ右と2つ右のセルに合わせて10と書いて、
そこがエミュレータの現在のヘッドの場所だと示す。そして右に進み、3k + 1, 3k + 2
番目のセルが合わせて00になってるところを見つけたら01にして左に戻り、10の
エミュレータの現在ヘッド位置まで戻りエミュレートを再開する。
このようなマシンの構成のために、まずエミュレート用の状態数n個を用意して、
エミュレータのヘッドの状態と読み取った文字(0 or 1)を記憶するための状態として
2n個、今いるセルがエミュレータのヘッド位置から右に 1, 2, 3k, 3k + 1, 3k + 2番目
なのかを記憶するため2n個の5倍、そして往路なのか復路なのかを記憶するのにさらに2倍
よって n + n * 2 * 5 * 2 = 21n 個の状態数があれば足りる。
省いた理由が分かってくれるとうれしいな。
あ、巨大数探索スレだから一つ巨大数を提示してからにしよう。
X = "「自然数論から矛盾の導出を試みて導出したら停止する計算機械」が
停止するまでにかかるステップ数"
自然数論が無矛盾ならXの存在を証明できないし、ゲーデルの不完全性定理より
Xの存在の否定も証明できない。
そして、任意の n ∈ {0, 1, 2, ...}について、 n < X が証明可能、すなわち
0 < X, 1 < X, 2 < X, ... がいずれも証明可能である。
これを巨大数と認めるかどうかは哲学の問題だから俺は言及しない。
定義が曖昧過ぎませんかねえ
哲学とか言う前に
別にそこはどうでも良いよ
21倍も状態を持てば押さえ込むのは簡単だし
そんなことをしなくとも
シフト関数と大差ないわけだし
矛盾していれば停止する
無矛盾を前提にすると停止しないので値は存在しない
u-1も超準数である。
以下u-2,u-3,・・・とつづき無限下降列となる
コンパクト性と相いれないのは変だな、自分がどっかで何かを勘違いなり間違いなりしてるんだろう
有限個のチューリングマシンの中には有限時間で停止するチューリングマシンが有限個存在する。
有限時間で停止するチューリングマシンの出力する情報の容量なり停止するまでのステップ数なりは有限
有限個の値の中には最大値が存在する。
ビジービーバー関数がこれ以上公理を仮定する必要が無くwell-definedであり、
普通の自然数を返すこと自体は明らかじゃないか？
100〜のスレッドの続きを読む