圖靈機

電腦科學的核心概念

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

從自動機到圖靈機

• 有限自動機： 記憶體有限，能處理正規語言。
• 下推自動機： 以堆疊為記憶體，能處理上下文無關語言。
• 圖靈機： 記憶體無限（無限紙帶），可解所有可計算問題。

什麼是圖靈機？

圖靈機

• 具無限紙帶的抽象機器。
• 讀寫符號。
• 能模擬任何演算法。

用類比理解圖靈機

廚房與廚師作為圖靈機

• 操作台是 紙帶。
• 操作台的區段是 格子。
• 食材是 符號。
• 廚師是 讀寫頭，負責讀取與寫入。
• 食譜是 程式，指導整個流程。

為何圖靈機重要？

圖靈機與可計算性

• 能模擬任何演算法
• 劃定電腦可解問題的邊界
• 引入不可判定問題概念（例如停止問題）
• 奠定現代計算理論基礎

停止問題

• 問題： 能否預測某程式對特定輸入會停止（結束）或永遠執行？
• 圖靈的洞見： 不存在能解決所有程式的通用演算法。
• 結果： 停止問題不可判定，有些問題沒有演算法解。
• 影響： 計算的侷限影響密碼學與 AI。

一起來練習吧！

電腦科學的核心概念