計算可能性理論 - Wikipedia
この記事には複数の問題があります。改善やノートページでの議論にご協力ください。 出典がまったく示されていないか不十分です。内容に関する文献や情報源が必要です。（2021年3月） 出典は脚注などを用いて記述と関連付けてください。（2017年10月） 出典検索?: "計算可能性理論" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL この記事は、全部または一部が他の記事や節と重複しています。 具体的には再帰理論との重複です。 記事のノートページで議論し、 重複箇所を重複先記事へのリンクと要約文にする（ウィキペディアの要約スタイル参照）か 重複記事同士を統合する（ページの分割と統合参照）か 重複部分を削除して残りを新たな記事としてください。 （2023年12月） 計算可能性理論（けいさんかのうせいりろん、英:
チャイティンのオメガΩ - 小人さんの妄想
「チャイティンのオメガΩ」とは何か。 それは「真の乱数」だ。 真の乱数、というのは「その数字そのものをもってしか表現することができない数」のことである。 例えば円周率3.141592...は、一見するとでたらめな数字の並びのようだが、「直径に対する円周の長さ」という簡潔な表現を持つ。 黄金比 1.618033... は、実は「正五角形の一辺と対角線との比」のことである。 ところが「チャイティンのオメガΩ」は、このような簡潔な表現を持つことができない。 他に例えようのない「真の乱数」なのである。 以下の説明の前に、予備知識として 不完全性定理の最短理解 d:id:rikunora:20080524 チューリングマシンは何を示したのか d:id:rikunora:20080525 を読んでおいた方がよいでしょう。 「チャイティンのオメガΩ」とは、「チューリングマシンの停止確率を表す数」のことで
チャイティンの定数 - Wikipedia
チャイティンの定数（チャイティンのていすう、英: Chaitin's constant）は、計算機科学の一分野であるアルゴリズム情報理論の概念で、非形式的に言えば無作為に選択されたプログラムが停止する確率を表した実数である。グレゴリー・チャイティンの研究から生まれた。停止確率（ていしかくりつ、英: Halting probability）とも。 停止確率は無限に多数存在するが、Ω という文字でそれらをあたかも1つであるかのように表すのが普通である。Ω はプログラムを符号化する方式に依存するので、符号化方式を特定せずに議論する場合は Chaitin's construction と呼ぶことがある。 個々の停止確率は正規かつ超越的な実数であり、計算不可能である。つまりその各桁を列挙するアルゴリズムは存在しない。 背景[編集] 停止確率の定義は「接頭属性のある完備計算可能関数」の存在に依存してい
ゲーデルを超えて オメガ数が示す数学の限界
数学の論理構造は完璧──というのは実は幻想にすぎない。かつてゲーデルの「不完全性定理」がこの事実を示したが，いま注目されるのは「オメガ」という数だ。完全に定義でき，確定値を持つのに，決して計算しきれない数とは？ ゲーデルは，数学が不完全であり，きちんと証明できないにもかかわらず正しい記述を含んでいることを示した。ところが「オメガ」という特別な数は，数学にさらに大きな不完全性が存在することを明らかにした。有限個の公理をいかに組み合わせても証明できない定理が，無数にあるのだ。したがって数学の「万物理論」はありえない。 オメガは，あるコンピューターに関して考えうるすべてのプログラムの集合から１つのプログラムをランダムに選んだ時，そのプログラムがいずれ停止するものである確率だ。完全にきちんと定義され，決まった値を持つ。しかし，どんな有限プログラムを使っても，オメガのすべての桁の値を計算し尽くすこと
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
