計算の理論

計算とはなんであるか

解ける問題と解けない問題

議論を簡単にするため、判定問題 decision problemだけを考える

与えられた文字列に対するなんらかの主張の真偽飲みを答えるという問題のことを言う

Q. 有限状態機械とチューリング機械は何が異なるか？