圖靈機五分鐘簡介

前言

本文的引用資料來自 Queen Mary University of London 的課程，部分圖片重製自該大學的上課講義，並依我的主觀意識做了修剪試圖讓內容讀得比較順暢&精簡(比方說原文是用巧克力舉例，但本文把這部分直接用顏色取代)。

圖靈機是甚麼？

圖靈機試圖去讓運算的過程完全交由機器透過固定的規則加以執行，原理是把運算的過程分割到最基本的操作，再由這些基本的操作負責所有運算。

可以把行走過程的指令都打在紙條上，並由圖靈機加以執行

比方說今天想要去學校上課，這時候我們可以把所有的操作區分成：前進、後退、左轉、右轉，接著用一條長長的紙帶去記錄每個操作的順序與次數，往後每次執行這條磁帶就可以讓我抵達學校。

圖靈機包含哪些零件？

圖靈機對應到的零件們

• 符號：代表每一個資料，可以包含空白 (Blank)
• 無限長的磁帶：負責將所有需要的符號記錄在上頭
• 讀寫頭：可以改寫或讀取磁帶上特定位置的資料
• 有限種類的狀態：代表當下運算的狀態種類，必須包含啟動與結束
• 狀態暫存器：負責記錄目前的狀態
• 操作表：代表狀態與符號對應到的操作

來看看加法圖靈機的過程吧！

比方說我們現在有個加法器，這裡我們用簡單的方式表達數字：連續幾個白色塊就代表數字幾，也就是在下面圖中我們想要執行的是 3 + 5。

首先狀態為綠色，讀寫頭讀到的符號為白色，對應操作表中應該執行：

1. 寫入黑色
2. 往右移動
3. 改狀態為棕色

再來狀態變為棕色，讀寫頭讀到的符號為白色，對應操作表中應該執行：

1. 不寫入
2. 往右移動
3. 改狀態為棕色

再來狀態還是棕色，讀寫頭讀到的符號為白色，對應操作表中應該執行：

1. 不寫入
2. 往右移動
3. 改狀態為棕色

最後狀態還是棕色，讀寫頭讀到的符號為黑色，對應操作表中應該執行：

1. 寫入白色
2. 往右移動
3. 改狀態為紅色

結束後會發現連續的白色區塊數目為 8 個，就完成我們想要的 3+5 = 8 啦！

通用圖靈機(Universal Turing Machine)

但上述的圖靈機實在是很不聰明，也只能執行特定的運算，像在這裡就只能執行簡單的加法，雖說我們也可以為特定的功能都量身打造一個圖靈機，不過很明顯地這樣做的效益實在是有點低，因此通用圖靈機(Universal Turing Machine)便應運而生。

你可以把通用圖靈機(Universal Turing Machine)想像成專門用來產出其他特定功能的圖靈機的圖靈機(實在有點繞口)。

通用圖靈機根據我們的需要產出相對應的圖靈機來使用，常用的程式語言本身就可以看作是一種通用圖靈機，而平時所寫的程式碼都會交由通用圖靈機加以執行並據此製造出另外一台圖靈機：根據我們所寫的邏輯加以運算的特定用途圖靈機─也就是執行檔(.exe)啦。

工商服務

這是我開的粉專，偶爾寫一些廢文，覺得有幫助的話可以幫我點個讚，揪感溫。