非決定性チューリングマシン
非決定性チューリングマシンとは、ある状態と読み取った文字から次の状態が一意に決まらず、複数の可能性を同時に分岐して探索できる仮想的な計算モデルです。計算複雑性理論において、P問題とNP問題の定義や比較を行う際の根幹となる重要な概念です。
理論計算機科学のAI用語一覧
4件理論計算機科学に関するAI用語を4件掲載しています。意味や使い方、関連用語を一覧から確認できます。
P問題
P問題とは、多項式時間という現実的な計算時間内で効率的に解を求められる決定性チューリングマシンの判定問題のクラスです。現代のコンピュータサイエンスやAIの計算限界を理解する上で、NP問題との比較やアルゴリズム設計の基礎となる極めて重要な概念です。
汎用チューリングマシン
汎用チューリングマシンとは、あらゆるチューリングマシンの動作をテープ上のプログラムとして読み込んで模倣できる、近代コンピュータの理論的基礎となった抽象機械のことです。
計算不能問題
計算不能問題とは、どのようなコンピュータ（アルゴリズム）を用いても、有限時間内に正しい「はい」または「いいえ」の答えを常に導き出すことが不可能な決定問題のことです。人工知能やソフトウェア開発における、理論上の限界を示す重要な概念として知られています。