問題解決：圖靈機

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

回顧

在嘗試學習圖靈機之前，您應該確保您熟悉 有限狀態機 來自 AS 計算規範和 A2 課程中新增的少數附加 FSM 概念。

定義

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

通用圖靈機

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

UTM 不像單個機器中的每個單獨程序一樣，它接受兩個輸入

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

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

機械圖靈機的例子

• 經典風格的圖靈機 有一個很棒的影片，展示了物理圖靈機的執行。

模擬

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

示例問題

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

複習

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