http://75.2.66.110/mediawiki/index.php?action=history&feed=atom&title=%E3%83%86%E3%83%B3%E3%83%97%E3%83%AC%E3%83%BC%E3%83%88%3APortal%3A%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%2F%E7%89%B9%E9%9B%86%E9%A0%85%E7%9B%AE 2026-04-29T19:29:29Z このウィキのこのページに関する変更履歴 MediaWiki 1.25.1 http://75.2.66.110/mediawiki/index.php?title=%E3%83%86%E3%83%B3%E3%83%97%E3%83%AC%E3%83%BC%E3%83%88:Portal:%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF/%E7%89%B9%E9%9B%86%E9%A0%85%E7%9B%AE&diff=9393&oldid=prev 2007-07-08T13:02:48Z

<p>Template:Portal:コンピュータ/特集項目</p> <p><b>新規ページ</b></p><div>'''[[計算可能性理論]]'''（computability theory）では、[[チューリング機械]]などの[[計算模型]]でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる。[[計算理論]]や[[数学]]の一分野である。<br /> <br /> 計算可能性は[[計算複雑性]]の特殊なものともいえるが、ふつう複雑性理論といえば[[チューリング機械|計算可能函数]]のうち計算資源を制限して解ける問題を対象とするのに対し、計算可能性理論は計算可能函数またはより大きな問題クラスを主に扱う。<br /> <br /> [[計算機科学]]の中心的課題の1つは、コンピュータを使って解ける問題の範囲を理解することでコンピュータの限界に対処することである。コンピュータは無限の計算能力を持つと思われがちだし、十分な時間さえ与えられればどんな問題も解けると想像することは易しい。しかし、多大な[[計算資源]]を与えられたとしても、見たところ単純な問題を解くことでコンピュータの能力の限界を明確に示すことは可能である。<br /> <br /> 計算可能性理論では、次の質問に答えることでコンピュータの能力を明らかにする。すなわち「ある[[形式言語]]と文字列が与えられたとき、その文字列はその形式言語に含まれるか？」である。この質問はやや難解なので、もう少し判り易く例を挙げる。言語として、全ての素数を表す数字列の集合を言語として定義する。入力文字列がその形式言語に含まれるかどうかという質問は、この場合、その数が素数であるかを問うのと同じことである。……[[計算可能性理論|もっと読む]]</div>

腹立つ