可計算性

電腦科學的核心概念

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

什麼是可計算性？

可計算問題

• 演算法存在： 有明確步驟可依。
• 有限時間： 在有限步驟內產生輸出。

不可計算問題

• 無演算法： 無法對所有可能輸入求解。
• 無限計算： 可能永遠無法得出結論。

¹ 一旦找到演算法，和／或讓已知演算法在有限時間內結束，原本不可計算的問題就能成為可計算問題。

自動機

自動機的定義

• 假想的機器
• 幫助我們理解計算如何運作
• 具有狀態
• 有在狀態間轉換的規則

有限自動機（FA）

有限自動機（FA）

• 簡單的「機器」
• 固定數量的狀態
• 除當前狀態外無記憶

下推自動機（PDA）

下推自動機（PDA）

• 更強大
• 具有狀態
• 以堆疊記憶做較複雜的判斷

重點總結

有限自動機（FA）

• 適用於簡單任務

下推自動機（PDA）

• 更能處理複雜問題

重要性

• 若問題可用自動機建模，就能以演算法加以解決

一起來練習吧！

電腦科學的核心概念