身心障礙人員考試身障四等-資訊處理類科計算機概要105 年第 24 題單選題
下列有關圖靈機（Turing machine）的敘述，何者錯誤？
A圖靈機的組成元件有控制器（control unit）、讀寫頭（read/write head）以及磁帶（tape）
B磁帶上可使用的字母符號（symbol）是一個有限集合（finite set）
C磁帶的長度是有限的（finite）正確答案
D圖靈機運作時的狀態（state）是有限的
C正確答案
圖靈機的磁帶長度是無限延伸的，其他三項（控制器+讀寫頭+磁帶、有限字母、有限狀態）都是正確描述。
為什麼答案是 C
錯誤！圖靈機的磁帶長度是「無限」的（可向一端或兩端無限延伸），這正是圖靈機比有限狀態機強大的關鍵——擁有無限記憶空間。
載入中…
完整詳解
Pro · 無限重點 圖靈機的磁帶長度是無限延伸的，其他三項（控制器+讀寫頭+磁帶、有限字母、有限狀態）都是正確描述。
記住圖靈機唯一「無限」的東西就是磁帶長度，其他全是 finite。
逐選項分析
A✕
圖靈機三大組件：控制器（狀態轉移邏輯）、讀寫頭（讀取與寫入符號）、磁帶（儲存資料），描述正確。
B✕
磁帶上使用的符號集合必須是有限的字母表（finite alphabet），這是形式語言與自動機理論的基本定義。
C✓ 正確
錯誤！圖靈機的磁帶長度是「無限」的（可向一端或兩端無限延伸），這正是圖靈機比有限狀態機強大的關鍵——擁有無限記憶空間。
D✕
圖靈機的內部狀態集合 Q 是有限的，狀態轉移函數也定義在有限狀態上，此為正確敘述。
圖靈機的「有限」vs「無限」
| 項目 | 有限/無限 | 說明 |
|---|
| 狀態集合 Q | 有限 | 控制器的狀態數量固定 |
| 字母符號 Σ/Γ | 有限 | 磁帶上可寫入的符號種類有限 |
| 磁帶長度 | 無限 ✅ | 可向右（或雙向）無限延伸 |
| 讀寫頭 | 1 個 | 一次讀/寫一格 |
