計算可能性

コンピュータサイエンスの基礎概念

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

計算可能性とは？

計算可能な問題

• アルゴリズムの存在: 明確な手続きが存在する。
• 有限時間: 限られた手順で出力を得る。

非計算可能な問題

• アルゴリズム不存在: すべての入力に対して解けない。
• 無限計算: 結論に到達しない場合がある。

¹ 既知のアルゴリズムを有限時間で終わらせる、または新しいアルゴリズムを見つけることで、非計算可能な問題が計算可能になることがあります。

オートマトン

オートマトンの定義

• 仮想の機械
• 計算の仕組みを理解する助けになる
• 状態をもつ
• 状態遷移の規則をもつ

有限オートマトン（FA）

有限オートマトン（FA）

• 単純な「機械」
• 状態数は固定
• 現在状態以外の記憶なし

プッシュダウン・オートマトン（PDA）

プッシュダウン・オートマトン（PDA）

• さらに強力
• 状態をもつ
• 複雑な判断のためのスタック型メモリをもつ

まとめ

有限オートマトン（FA）

• 単純な課題に有用

プッシュダウン・オートマトン（PDA）

• より複雑な問題に強力

重要性

• 問題がオートマトンでモデル化できれば、解くアルゴリズムを実装できる

練習しましょう！

コンピュータサイエンスの基礎概念