Learning Objectives
- 說出圖靈機的組成（紙帶、讀寫頭、狀態、規則表），並能照規則表追蹤它的執行
- 說明「規則表就是程式」與通用圖靈機的意義
- 用自己的話說明停機問題：不存在能判斷所有程式會不會停的通用方法
- 分辨「找答案」與「驗證答案」的難度差異，說出 P 與 NP 問題在問什麼
- 面對隱私、演算法偏誤、AI 的責任、數位落差、智慧財產的情境，說出應該考慮的原則
電腦有做不到的事嗎
手機上的 App 偶爾會卡住、一直轉圈圈。你也許想過：作業系統能不能在程式卡死之前就先看出來，「這個程式會永遠跑下去」？
這個問題聽起來是工程問題，答案卻是數學：不可能做出一個對所有程式都判斷正確的檢查工具。不是現在的技術不夠，而是邏輯上就做不到。
這是本軌道的最後一課，分成兩部分：
- 計算理論：電腦的能力有沒有極限？什麼是「可以計算的」？哪些問題就算可以算，也算得太久？
- 數位倫理：電腦能做的事越來越多，哪些事「應該」做、要怎麼做？個資、演算法偏誤、AI 的責任、數位落差、智慧財產都是你每天會碰到的問題。
圖靈機
1936 年，英國數學家圖靈（Alan Turing）發表論文〈On Computable Numbers, with an Application to the Entscheidungsproblem〉。當時還沒有今天的電腦，他想回答的是：「用機械式的步驟計算」到底是什麼意思？他設計了一個極簡的抽象機器，後人稱為圖靈機（Turing machine）：
| 組成 | 作用 |
|---|---|
| 紙帶 | 分成一格一格，兩端可以無限延伸；每格寫一個符號，沒寫的格子是空白 |
| 讀寫頭 | 每次對準一格，可以讀出、改寫那一格的符號 |
| 狀態 | 機器目前「在做哪一個階段的工作」，例如「往右找結尾」「處理進位」 |
| 規則表 | 寫著「在某個狀態、讀到某個符號時，要寫入什麼、往左或往右移一格、換到哪個狀態」 |
機器的每一步都一樣：
讀目前這一格 → 依（狀態, 讀到的符號）查規則表 → 寫入 → 移動讀寫頭 → 換狀態
進入「停機」狀態就結束，紙帶上留下的就是答案。
規則這麼簡單，能算的東西卻很多。今天的電腦能算的，圖靈機在原則上都能算（只是慢很多）；反過來，圖靈機算不出來的，電腦也算不出來。丘奇–圖靈論題（Church–Turing thesis）主張：任何「照步驟機械式完成」的計算，都可以用圖靈機完成。它不是被證明的定理，而是被廣泛接受的對「可計算」的定義。
用 Python 寫一台圖靈機
圖靈機的執行引擎只有幾行：讀、查表、寫、移動。這支程式用字典當規則表、用串列當紙帶，計算 1011 加 1。上方的格子是紙帶，▲ 是讀寫頭 head 的位置。注意讀寫頭先一路往右，碰到空白才回頭處理進位。
規則表就是程式
剛剛三個程式用的是同一個執行引擎，差別只在規則表。換一張規則表，同一台機器就做不同的事；這和第 01 課說的「換一個程式，同一台機器就能做完全不同的事」是同一個想法。
圖靈在同一篇論文裡更進一步：把某台圖靈機的規則表寫成符號放在紙帶上，就可以設計一台「讀別台機器的規則表，然後照著執行」的機器，稱為通用圖靈機（universal Turing machine）。程式本身也是一種資料，可以存起來、被另一個程式讀取與執行，這正是今天的電腦能安裝並執行任何軟體的原理，也和第 10 課的「程式與資料放在同一個記憶體」相呼應。
下一個練習換你修改規則表。
停機問題：有些問題沒有任何程式能解
「一直往右走」看規則就知道不會停。但一般的程式很複雜，能不能寫一個檢查工具，對任何程式與輸入都正確回答「會不會停」？
圖靈 1936 年的論文已經用類似下面的論證，說明有些問題沒有任何機器能解。今天教科書把它整理成停機問題（halting problem；這個名稱是後人取的）。用 Python 的寫法說明如下（這是思考實驗，不能真的執行）：
# 假設有人寫出了萬能的檢查工具：
# halts(p, x) 回傳 True → 程式 p 吃輸入 x 會停
# halts(p, x) 回傳 False → 會永遠跑下去
def trouble(p):
if halts(p, p): # 問：p 拿自己當輸入，會停嗎？
while True: # 會停的話，我就故意永遠不停
pass
else:
return # 不會停的話，我就立刻停
現在問：trouble(trouble) 會停嗎？
| 如果 halts 說… | trouble 實際上會… | 結果 |
|---|---|---|
| 會停（True） | 進入無窮迴圈，不停 | halts 答錯 |
| 不會停（False） | 立刻 return，停了 | halts 答錯 |
不管 halts 怎麼回答都是錯的，所以「對所有程式都正確的 halts」不可能存在。這就是不可計算（uncomputable）的問題：不是算得慢，而是沒有任何程式能對所有情況給出正確答案。
這對實務有什麼影響
- 沒有任何工具能完美找出所有會卡死的程式，或完美判斷所有程式是不是惡意程式。實務上的工具都是「能抓到很多、但不保證全部」，或用逾時強制中止。
- 「判斷兩個程式的行為是否完全相同」這類問題也同樣沒有通用解法，所以軟體需要測試，也需要人來檢查。
- 限制是「所有程式」：對特定的程式，常常還是能證明它會停或不會停。
想一想：圖靈機與停機問題
一台圖靈機的規則只有兩條：在狀態 A 讀到 1 → 寫 0、往右、留在 A；在狀態 A 讀到空白 → 不動、停機。紙帶上是 111，讀寫頭從最左邊的 1 開始。下面的 Python 程式模擬它，會印出什麼？
tape = list('111_')
head = 0
state = 'A'
rules = {('A', '1'): ('0', 1, 'A'), ('A', '_'): ('_', 0, 'halt')}
while state != 'halt':
write, move, state = rules[(state, tape[head])]
tape[head] = write
head += move
print(''.join(tape).strip('_'), head)
有一家公司宣稱推出了一個工具，能對任何程式與輸入，正確判斷它會不會進入無窮迴圈。根據停機問題，下列哪個說法正確？
數獨：檢查一個填好的盤面對不對很快，但從空白盤面推出答案，在一般化成很大的盤面時可能要試非常多種可能。這種「答案很容易驗證」的問題屬於哪一類？
算得出來，但要算多久：P 與 NP
停機問題是「根本算不出來」。另一類問題算得出來，但可能要算到天荒地老。
第 24 課介紹過用步驟數的成長來衡量演算法。計算理論把問題分成幾類：
| 類別 | 意思 | 例子 |
|---|---|---|
| P | 有方法可以很快找到答案（步驟數是輸入大小的多項式，例如 n²、n³） | 排序、找最短路徑 |
| NP | 給一個候選答案，可以很快驗證它對不對 | 數獨、排課表、背包裝箱、下面的「挑數字湊總和」 |
所有 P 的問題都屬於 NP（能很快找到答案，當然也能很快驗證）。問題是反過來：「很快能驗證」的問題，是不是都「很快能找到」？ 這就是 P 與 NP 問題，由 Stephen Cook 在 1971 年的論文中正式提出，到今天仍然沒有人證明或否定，是電腦科學最著名的未解問題之一。多數研究者相信 P 不等於 NP。
它和上一課也有關：很多密碼學方法的安全性，就建立在「有些問題驗證容易、但找答案很難」上，例如 RSA 依賴的「大數分解」。
下面這支程式示範兩者的差距。
找答案與驗證答案
從 [3, 9, 8, 4] 挑幾個數字，讓總和剛好是 15。程式先試挑 1 個的所有組合，再試挑 2 個、3 個……注意 tries（試了幾組）一直增加，而最後一行「驗證」只做了一次加總。
數位倫理：隱私與個人資料
接下來的問題不是「電腦能不能做」，而是「應不應該做、要怎麼做」。
個人資料
個人資料是能直接或間接識別出某個人的資料：姓名、身分證字號、學號、電話、地址、照片，也包括病歷、位置紀錄這類敏感資料。單獨一項看不出是誰，但和其他資料組合起來就能認出來的，也算。
臺灣有《個人資料保護法》，歐盟有《一般資料保護規則》（GDPR）。各地法律細節不同，但有幾個共同的原則：
| 原則 | 意思 |
|---|---|
| 告知 | 蒐集時說清楚：誰蒐集、做什麼用、保存多久 |
| 特定目的、最小必要 | 只蒐集這個目的需要的資料，不多收；不拿去做原本沒說的用途 |
| 當事人的權利 | 本人可以查詢、要求更正，也可以在一定條件下要求刪除或停止使用 |
| 安全維護 | 蒐集的人要負責保護，避免外洩 |
去識別化不等於安全
把姓名拿掉，資料還是可能被認出來：郵遞區號、生日、性別這幾欄組合起來，往往就足以縮小到很少的人。公開或分享資料前，要想的是「和其他資料合起來，能不能認出是誰」。
你的數位足跡
你在網路上的每次搜尋、按讚、定位，都可能被記錄與分析。保護自己的做法：看清楚 App 要求的權限、定期檢查隱私設定、不在公開的地方貼出證件或課表這類能拼出你行蹤的資訊。
演算法偏誤與 AI 的責任
演算法偏誤
機器學習模型從資料中學規律。資料裡有偏差，模型就會學到偏差，而且會用很有效率的方式大量複製。常見的來源：
| 來源 | 例子（假設情境） |
|---|---|
| 歷史資料本身有偏見 | 用過去十年的錄取資料訓練履歷篩選模型，過去錄取者大多是某一性別，模型就可能壓低另一性別的分數 |
| 資料不具代表性 | 臉部辨識的訓練照片大多來自某些族群，對其他族群的錯誤率就比較高 |
| 量測方式不公平 | 用「過去的就醫花費」代表「健康需求」，就醫機會少的人看起來需求比較低 |
| 回饋迴路 | 模型決定把資源投到哪裡，那裡就產生更多資料，讓模型更相信原本的判斷 |
對策包括：檢查資料來自哪些人、分別比較不同群體的錯誤率、讓受影響的人有申訴與要求人工複查的管道。
AI 的責任
AI 系統做出影響人的決定時，至少要問三件事：
- 誰負責？ 出錯時，開發者、部署的單位、使用者各自要負什麼責任，必須事先講清楚；「是 AI 決定的」不能當作沒有人負責的理由。
- 能不能解釋？ 被拒絕貸款或入學的人，有權知道大致的理由。
- 人在哪裡？ 重大的決定（醫療、司法、聘用、成績）應該由人做最後判斷，AI 提供參考。
使用生成式 AI 的人也有責任。它會產生看起來很合理、但實際上錯誤的內容（例如不存在的參考文獻）。用它寫報告時，事實與引用要自己查證，並依照課程或單位的規定說明怎麼使用了 AI。
數位落差與智慧財產
數位落差
數位落差（digital divide）是不同的人在使用數位科技上的差距，有好幾個層次：
| 層次 | 例子 |
|---|---|
| 有沒有設備與網路 | 偏遠地區網路不穩、家裡只有一支手機要全家共用 |
| 會不會用 | 長輩不會用網路銀行、不知道怎麼辨認詐騙訊息 |
| 能不能用得好 | 會用搜尋，但不會判斷資料的可信度 |
設計系統時，無障礙（讓視障、聽障、行動不便的人也能使用）、在網路慢或舊手機上也能用、保留非數位的替代管道，都是縮小落差的做法。
智慧財產與授權
軟體、文章、圖片、音樂都受著作權保護。著作權保護的是表達方式，不是想法本身：你可以用自己的程式實作同一個演算法，但不能直接複製別人的程式碼當成自己的。
| 授權方式 | 意思 |
|---|---|
| 專屬授權（商業軟體） | 只能依授權條款使用，通常不能複製、修改、轉散布 |
| 自由及開放原始碼授權（例如 MIT、GPL） | 可以使用、修改、散布；條件依授權而不同，例如 GPL 要求修改後散布時也要公開原始碼 |
| 創用 CC（Creative Commons） | 作者事先標示允許的用法，例如「姓名標示」「非商業性」「禁止改作」 |
在臺灣，《著作權法》也有「合理使用」的規定，例如為了教學、評論在合理範圍內引用；但範圍要依個案判斷，不是「標了出處就可以全部拿來用」。
生成式 AI 用大量網路資料訓練，訓練資料的使用與產出內容的著作權歸屬，各國的法律與判決都還在討論中。使用時，避免要求它重製特定作品，並遵守各平台與單位的規定。
想一想：數位倫理的情境
社團舉辦一日迎新活動，報名表要求填寫姓名、手機、身分證字號、血型、家庭年收入。依照「特定目的、最小必要」原則，比較好的做法是？
一家公司用過去十年的錄取者履歷訓練篩選模型，而過去錄取的人大多是同一性別。最可能出現的問題是？
你用生成式 AI 工具協助寫報告，交出去後才發現其中兩篇參考文獻根本不存在。誰該負責，以後怎麼做？
重點整理
- 圖靈機由紙帶、讀寫頭、狀態、規則表組成；每一步讀、查表、寫、移動、換狀態。圖靈在 1936 年的論文提出這個模型。
- 規則表就是程式；通用圖靈機能讀取並執行別台機器的規則表，是「程式也是資料」、電腦能執行任何軟體的理論基礎。
- 丘奇–圖靈論題：機械式步驟能完成的計算，圖靈機都能完成。
- 停機問題：不存在能對所有程式與輸入正確判斷「會不會停」的程式。有些問題是不可計算的，與電腦快慢無關。
- P 與 NP：P 是能很快找到答案的問題，NP 是能很快驗證答案的問題；P 是否等於 NP 至今未解。很多密碼學依賴「驗證容易、找答案難」。
- 隱私：個資是能直接或間接識別個人的資料；蒐集要告知、有特定目的、只收必要的；去識別化不等於安全。
- 演算法偏誤來自資料與設計；要分群體檢查結果，保留申訴與人工複查。AI 做出的決定仍要有人負責，生成式 AI 的內容要查證。
- 數位落差有設備、能力、運用三個層次；智慧財產保護的是表達，使用他人作品要看授權。
這是計算機概論軌的最後一課。從位元、邏輯閘、CPU、作業系統、程式、資料庫、網路到資訊安全，你已經走完電腦運作的整條路。 想實際寫程式，可以接著上 Python 軌；想深入演算法與複雜度，可以上演算法軌；想進一步了解怎麼負責任地使用 AI，可以上 AI 素養軌。