計算不能関数と判定不能問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/02/29 16:21 UTC 版)
「計算可能関数」の記事における「計算不能関数と判定不能問題」の解説
あらゆる計算可能関数にはその計算方法を示す有限な手続きが存在するので、計算可能関数は数え上げられるだけの個数しかない。自然数についての有限関数は数え上げられないほど無数にあり、その多くは計算可能ではない。ビジービーバー関数はそのような計算不能な関数の具体例である。 同様に自然数の部分集合の多くは計算可能ではない。チューリングマシンの停止問題はそのような計算不能な集合の例である。ダフィット・ヒルベルトの提唱した Entscheidungsproblem（決定問題）は（自然数で符号化された）数学的な文が真であるかどうかを決定する実効的な手続きがあるかどうかを問うものであった。これについて1930年代にチューリングとチャーチは個別に決定不能であることを示した。チャーチ＝チューリングのテーゼによれば、そのような計算を行える実効的な手続き（アルゴリズム）は存在しない。
※この「計算不能関数と判定不能問題」の解説は、「計算可能関数」の解説の一部です。
「計算不能関数と判定不能問題」を含む「計算可能関数」の記事については、「計算可能関数」の概要を参照ください。
ウィキペディア小見出し辞書の「計算不能関数と判定不能問題」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 計算不能関数と判定不能問題のページへのリンク
