数学基礎論・数理論理学 その19 (550ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
271(3): 2024/05/14(火)15:19 ID:wqV6CtwU(1/6) AAS
>>226
自然数の帰納的関数であるこれってどうコーディングされるの？
a,b,cは自然数
Xは0個以上の非負整数
a#bはb個のa
a{}0=a
a{}b=1+(a{}(b-1))
a{0}0=0
a{0}b=a{}(a{0}(b-1))
a{c}0=1
a{c}b=a{c-1}(a{c}(b-1))
g()=1{}1{}1
g(0)=g(){}1
g(a)=g(){g(a-1)}g()
G()=g(g(0){1}g())
G(0)=g(G())
G(a)=g(G(a-1))
G(0#c,0)=G(G()#c)
G(0#c,a)=G(G(0#c,a-1)#c)
G(X,b,0#c)=G(X,b-1,G()#c)
G(X,b,a)=G(X,b-1,G(X,b,a-1))
G(X,b,0#c,a)=G(X,b-1,G(X,b,0#c,a-1)#(c+1))
GG()=G(G()#G())
GG(0)=G(GG()#GG())
GG(a)=G(GG(a-1)#GG(a-1))
275(1): 2024/05/14(火)16:52 ID:wqV6CtwU(2/6) AAS
>>274
それは単純な式なら分かるけどさ
複数の式で定義されている
しかもその複数の式に使われている
帰納的な記法が一定の範疇に収まらないのを
どうするのかなと
276(1): 2024/05/14(火)17:00 ID:wqV6CtwU(3/6) AAS
人間が見て帰納的だと分かる記述でも
いくらでも記法を新しく追加できるから
あるコーディング手法で定義された関数全体が加算だったとして
そこで使われる帰納的記法に収まらない記法を使って記述される帰納的関数は
そのコーディング手法では記述できないから
その帰納的関すに使われた記法も含めたさらに大きなコーディング手法を導入してコーディングするんでしょ？
でもまたその範疇に収まらないのが出てきて・・・・って終わらないんじゃないの？
可算集合の可算なcofinalな集合は可算でも
帰納的記法はいくらでもつまり非可算でもあり得るんじゃ無い？
277(1): 2024/05/14(火)17:26 ID:wqV6CtwU(4/6) AAS
その困難を避けるには
どんな非可算に多い帰納的記法を使って定義した帰納的関数も
ある一定の記法にしたがって定義した帰納的関数と同じ関数になることを証明できればいいんだけど
はてさてソレ可能なのかしらん
だって人間の想像力は「無限大」で>>271みたいなへんてこな記述だって思いつくわけでしょ
278(1): 2024/05/14(火)17:28 ID:wqV6CtwU(5/6) AAS
各個撃破で>>271は一定の記法に書き直せるかもしれないけど
それじゃ安心できないんだなあ
279(1): 2024/05/14(火)18:09 ID:wqV6CtwU(6/6) AAS
ゲーデル数のようなコーディング手法によってすべての帰納的関数をfnと付番できたとすると
g(n)=max_(m<n)fm(n)
と定義した関数はいずれはどのfnよりも値が大きくなるから
gが帰納的関数なら
すべての帰納的関数よりいずれは大きくなるはずなのに
g<g+1だから矛盾よね
だからgは帰納的関数じゃ無いんだけど
この定義ってホントに帰納的な記述じゃないのかな？
ゲーデル数みたいなコーディング手法って算術化つまり数式で表せるんでしょ？
ならfnみたいな付番も帰納的にできるんじゃなくて？
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.028s