コトバンクはYahoo!辞書と技術提携しています。

計算可能性 けいさんかのうせいcomputability

世界大百科事典 第2版の解説

けいさんかのうせい【計算可能性 computability】

計算可能性とは,自然数等の離散構造上の関数で具体的に計算できる関数を数学的に定式化した概念である。あらかじめ与えられた規則に従い,偶然や独創性によらず機械的に記号を処理することがあらゆる計算に共通の特徴である。そのため,計算可能な関数は,メモリーがいくらでもある(理想化された)コンピューターで計算できる関数と一致する。
[歴史]
 計算可能性の概念は,計算とは何かという問いに答えようとする試みを通じて,1930年代にゲーデルチューリング,チャーチAlonzo Church(1903-95),クリーネStephen C.Kleene(1909-94)等の有力な論理学者のさまざまの提案を集大成し得られたものである。

出典 株式会社平凡社世界大百科事典 第2版について 情報

世界大百科事典内の計算可能性の言及

【チューリング機械】より

…以前に書いた記号は参照できるし,消して新しいものと書き換えてもよい。その後の計算可能性の理論や現代のコンピューターの発展を見ても,このチューリングの抽象化は正しかったといえる。他方,チューリングの時代に計算可能性に関していくつかの数学的提案があったが,これらはすべてチューリング機械と同等であることが証明された。…

※「計算可能性」について言及している用語解説の一部を掲載しています。

出典|株式会社平凡社世界大百科事典 第2版について | 情報

計算可能性の関連キーワードテューリング機械チューリング機械計算の理論離散数学

今日のキーワード

チームパシュート

スピードスケートや自転車競技の一。複数人でチームを組み、隊列を組んで一定の距離を走り、速さを競うもの。団体追い抜き競技。...

続きを読む

コトバンク for iPhone

コトバンク for Android