計算可能性理論

計算可能性理論 (けいさんかのうせいりろん) は、与えられた問題がある制約の下で解くことができるかどうか理論的に扱う学問。計算理論数学の一分野。

チューリングマシンが解くことのできる問題のクラスなどを扱う。

関連項目