チャーチ＝チューリングのテーゼの内容として、適切なものはどれか。

解説

正解は「直観的に計算可能な関数は、チューリング機械で計算できる関数と一致する」です。機械的な手順（アルゴリズム）で計算できるという直観的な概念を、チューリング機械という数学的なモデルで捉えられるという主張です。直観的な概念を対象とするため証明はできませんが、λ計算や帰納的関数など独立に提案された計算モデルがすべてチューリング機械と同等であることが示され、広く受け入れられています。「すべての問題は、チューリング機械で多項式時間で解ける」は誤りで、計算できない問題もあります。「クラス P とクラス NP は等しい」は未解決問題で、このテーゼとは無関係です。「チューリング機械で計算できる関数は、有限オートマトンでも計算できる」は、有限オートマトンの能力が真に低いため誤りです。