再帰理論 --ゲーデルの不完全性定理以後--（1930〜50年代） - とりマセ
某所で再帰理論の最近の研究の流れの話が出たので、せっかくなのでブログに纏めておきます。 数学基礎論の大きな分野のひとつとして、ゲーデルらの研究を発端として生まれた再帰理論。 では、ゲーデルの不完全性定理以後、数学基礎論の一分野である再帰理論は、どのような発展を遂げたのでしょうか。今回は、1950年代までの再帰理論の研究の歴史を辿ってみましょー。 1930年代 1930年代。チャーチ、ゲーデル、チューリング、クリーネその他多くの研究者による研究、そしてゲーデルの不完全性定理を発端の一つとして、計算可能性と計算不可能性の研究が始まりました。1930年代の計算論の研究の始まりは歴史的に非常に重要ですが、詳しい文献がたくさんあるので、ここでは省略します。 このような1930年代の研究によって、計算という概念が数学的に定義され、コンピュータ開発もたぶん順調に進むことになったのでしょう。しかし何よ
チャイティンのオメガΩ - 小人さんの妄想
「チャイティンのオメガΩ」とは何か。 それは「真の乱数」だ。 真の乱数、というのは「その数字そのものをもってしか表現することができない数」のことである。 例えば円周率3.141592...は、一見するとでたらめな数字の並びのようだが、「直径に対する円周の長さ」という簡潔な表現を持つ。 黄金比 1.618033... は、実は「正五角形の一辺と対角線との比」のことである。 ところが「チャイティンのオメガΩ」は、このような簡潔な表現を持つことができない。 他に例えようのない「真の乱数」なのである。 以下の説明の前に、予備知識として 不完全性定理の最短理解 d:id:rikunora:20080524 チューリングマシンは何を示したのか d:id:rikunora:20080525 を読んでおいた方がよいでしょう。 「チャイティンのオメガΩ」とは、「チューリングマシンの停止確率を表す数」のことで
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
読了『メタマス！』 - Personal_NewsN
Amazon.co.jp: 知の限界: G.J.チャイティン (著), 黒川利明 (翻訳): 本
