問題解決：圖靈機

來自規範：圖靈機和通用機。 圖靈機的抽象模型和通用機。

回顧

在嘗試學習圖靈機之前，您應該確保您熟悉來自 AS 計算規範的有限狀態機以及 A2 課程中新增的一些額外的 FSM 概念。

定義

圖靈機提供了一種通用的或正式的計算模型，可用於確定某個任務是否可計算。
或者
一種正式的計算模型，它由一個有限狀態機 (FSM) 組成，該有限狀態機控制一個或多個磁帶，其中至少一個磁帶具有無限長度（即無限長）。

通用圖靈機

通用圖靈機 (UTM) 是一種圖靈機，它可以透過模擬任何圖靈機的行為來執行其他圖靈機。如果一個序列是可計算的，那麼 UTM 將能夠執行它。UTM 的行為就像一個直譯器，這正是 PC 在執行 Java applet 或 Flash 指令碼時所做的。

UTM 不是在單個機器內處理每個單獨的程序，而是接受兩個輸入

• 執行計算所需的個別圖靈機的描述
• 計算所需的所有輸入

普遍性原理：通用機是一種能夠模擬任何其他機器的機器。

機械圖靈機的例子

• 一個“經典風格”的圖靈機有一個很棒的影片，描述了物理圖靈機的操作。

模擬

• 圖靈卡拉有一些很棒的說明，可以幫助您掌握圖靈機的基本操作。

示例問題

練習：圖靈機 什麼是圖靈機？ 回答 一個有限狀態機，它操作一個或多個磁帶，其中至少一個磁帶是無限長的。

複習

• 圖靈機抽認卡帶有測試和其他活動