計算可能性理論とは何？わかりやすく解説 Weblio辞書

計算可能性理論

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/24 16:25 UTC 版)

計算可能性理論（けいさんかのうせいりろん、英: computability theory）とは、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。

「計算可能性理論」の続きの解説一覧

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/09 06:43 UTC 版)

「計算理論」の記事における「計算可能性理論」の解説

詳細は「計算可能性理論」を参照計算可能性理論は、ある問題がコンピュータで解くことができるかどうかを扱う。チューリングマシンの停止問題は計算可能性理論における、ある意味で最も重要な成果である。定式化しやすく、かつチューリングマシンで解けない問題の具体例であり、数学基礎論との関係もある。同時に、静的に無限ループの検出を確実に行う方法は無いことを示している、といったように実応用的な意義もある。

※この「計算可能性理論」の解説は、「計算理論」の解説の一部です。
「計算可能性理論」を含む「計算理論」の記事については、「計算理論」の概要を参照ください。

ウィキペディア小見出し辞書の「計算可能性理論」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。お問い合わせ。

固有名詞の分類

学問	歯科インプラント学線形計画問題計算可能性理論土壌地理学映画史 >>固有名詞 >>方式・規則一覧 >>主義・方式一覧 >>学問一覧


	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアの計算可能性理論 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
	Text is available under GNU Free Documentation License (GFDL). Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの計算理論 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。