108 年 國立清華大學資訊系統與應用研究所丙組《計算機概論》

本題考驗對二補數（two's complement）表示法的理解，包含其最大最小值表示範圍以及二補數的加法運算。

(a) 七位元二補數能表示的最大最小值

對於一個 $n$ 位元的二補數系統：

• 所能表示的最大正整數是 $2^{n-1} - 1$。
• 所能表示的最小負整數是 $-2^{n-1}$。

在此問題中，位元長度 $n=7$。

• 最大值：$2^{7-1} - 1 = 2^6 - 1 = 64 - 1 = 63$。
• 最小值：$-2^{7-1} = -2^6 = -64$。

因此，七位元的二補數系統能表示的數字範圍是 $[-64, 63]$。

【答案】最大值為 63，最小值為 -64。

(b) 二補數加法運算與轉換

題目給定的運算是：

  1110010
+ 0010000
---------

這是一個七位元的二補數加法。我們直接進行二進位加法，並注意進位。

   1110010  (1110010₂)
+  0010000  (0010000₂)
---------
  1000010  (1000010₂)

接下來，我們需要將結果 $1000010_2$ 轉換回十進位。由於最高位元是 1，這是一個負數。在七位元的二補數系統中，最高位元（MSB）代表符號位元。

將 $1000010_2$ 轉換為十進位：
最簡單的方法是先將其視為無號數，然後再根據二補數規則處理。
$1000010_2 = 1 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4 + 0 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0$

核心觀念

這題考查錯誤更正碼的漢明距離（Hamming distance）。

兩個等長位元模式的漢明距離，是兩者在相同位置上位元不同的數量。先計算所有碼字之間的距離：

$d(A,B)=d(00000,00111)=3$

$d(A,C)=d(00000,11110)=4$

$d(A,D)=d(00000,11001)=3$

$d(B,C)=d(00111,11110)=3$

$d(B,D)=d(00111,11001)=3$

$d(C,D)=d(11110,11001)=3$

因此，最小漢明距離為：

$d_{\min}=3$

錯誤更正碼的重要定理如下：

• 最多可偵測的錯誤數：

$d_{\min}-1$

• 最多可更正的錯誤數：

$\left\lfloor \frac{d_{\min}-1}{2}\right\rfloor$

解題方法

（a）錯誤偵測與錯誤更正能力

由於：

$d_{\min}=3$

最多可偵測：

$d_{\min}-1=3-1=2$

因此，每組 5 位元最多可偵測 2 個錯誤。

最多可更正：

$$\left\lfloor \frac{3-1}{2}\right\rfloor = \left\lfloor 1\right\rfloor =1$$

因此，每組 5 位元最多可更正 1 個錯誤。

（b）解碼訊息

採用「最小漢明距離解碼」：收到一組位元後，計算它與四個合法碼字的距離，選擇距離最小者。

第一組：$10000$

$d(10000,A)=1$

$d(10000,B)=4,\quad d(10000,C)=3,\quad d(10000,D)=2$

距離 $A$ 最近，因此解碼為：

$10000\rightarrow A$

第二組：$01110$

$d(01110,A)=4$

本題主要考驗對位元操作，特別是循環位移（circular shift）的理解，以及十六進位與二進位之間的轉換。

(a) 右循環位移與左循環位移的等價性

對於一個長度為 $n$ 的位元字串，一個右循環位移 $k$ 位元，等價於一個左循環位移 $n-k$ 位元。
在這裡，位元字串長度 $n=8$ 位元。
右循環位移的位元數 $k=2$。

因此，右循環位移 2 位元等價於左循環位移 $8 - 2 = 6$ 位元。

【答案】6 位元。

(b) 十六進位位元模式的右循環位移

首先，我們需要將十六進位的位元模式 CF 轉換為二進位。
十六進位中的每個數字對應 4 個位元：

• C (十六進位) = 1100 (二進位)
• F (十六進位) = 1111 (二進位)

所以，CF (十六進位) = 1100 1111 (二進位)。
這是一個 8 位元的位元模式。

本題主要考查作業系統核心（Kernel）的功能與組成，以及核心與使用者程式之間的互動機制。

(a) OS Kernel 的四大主要軟體元件及其功能

作業系統核心（Kernel）是作業系統最核心的部分，負責管理系統資源並為應用程式提供服務。雖然核心的具體架構可能因作業系統而異，但通常包含以下幾個主要軟體元件：

1. 行程管理 (Process Management)

   • 功能： 負責建立、終止、排程（調度）以及同步和通訊使用者行程（process）和核心執行緒（thread）。它決定哪個行程或執行緒在何時運行，以及如何分配 CPU 時間。這包括處理行程之間的切換（context switching）。

2. 記憶體管理 (Memory Management)

   • 功能： 負責分配和回收系統的記憶體資源。它追蹤哪些記憶體區域正在被使用，哪些是空閒的，並決定行程的記憶體請求。這通常涉及虛擬記憶體（virtual memory）的管理，例如分頁（paging）和分段（segmentation），以提供行程獨立的記憶體空間並有效利用實體記憶體。

3. 檔案系統管理 (File System Management)

   • 功能： 負責管理儲存裝置上的檔案和目錄結構。它提供了建立、刪除、讀取、寫入、重命名檔案等操作的介面，並將這些操作映射到底層儲存硬體的讀寫指令。同時，它也負責管理檔案的權限和存取控制。

4. 裝置管理 (Device Management) / I/O 系統 (I/O System)

   • 功能： 負責管理系統的所有硬體裝置（如硬碟、網路卡、鍵盤、顯示器等）的輸入/輸出（I/O）操作。它透過裝置驅動程式（device drivers）與硬體互動，並為應用程式提供一個統一的介面來存取這些裝置，屏蔽底層硬體的複雜性。

其他可能的元件還包括：系統呼叫介面（System Call Interface）、網路堆疊（Network Stack）等，但上述四個是最基本且核心的組成部分。

(b) 核心收回使用者程式控制權的時機與機制

核心需要收回使用者程式的控制權，以確保系統的穩定性、安全性，並能公平地分配資源。

• 兩個核心需要收回控制權的例子：

  1. 系統呼叫 (System Call)： 當使用者程式需要執行特權操作（如讀寫檔案、建立新行程、存取硬體等）時，它不能直接執行這些操作，因為這

本題考查電腦網路的層級模型（Layered Architecture），特別是網際網路（Internet）的 TCP/IP 模型，以及不同層級協定在類似任務上的差異。

(a) 網際網路軟體（TCP/IP 模型）的四個層級及其功能

網際網路協定族（TCP/IP Model）是現代網路通訊的基礎。雖然有不同的版本（如四層模型或五層模型），這裡我們採用常見的四層模型：

1. 應用層 (Application Layer)

   • 功能： 負責為使用者應用程式提供網路服務。它定義了應用程式之間如何交換資料，以及如何格式化資料。常見的協定包括 HTTP (網頁瀏覽)、FTP (檔案傳輸)、SMTP (電子郵件傳送)、DNS (域名解析) 等。

2. 傳輸層 (Transport Layer)

   • 功能： 負責在端對端（end-to-end）的主機之間提供可靠或不可靠的資料傳輸服務。它將來自應用層的資料分割成較小的段（segment），並為每個段添加標頭（header），包含來源和目的埠號（port numbers），用於區分不同的應用程式。
   • 主要協定：
     • TCP (Transmission Control Protocol)： 提供可靠、有連接（connection-oriented）、流量控制（flow control）和擁塞控制（congestion control）的服務。
     • UDP (User Datagram Protocol)： 提供不可靠、無連接（connectionless）、盡力而為（best-effort）的服務，速度較快，但需要應用程式自行處理可靠性問題。

3. 網路層 (Network Layer) / 網際網路層 (Internet Layer)

   • 功能： 負責將資料包（packet）從來源主機路由到目的主機。它處理邏輯位址（如 IP 位址），並決定資料包在網路中的路徑。
   • 主要協定： IP (Internet Protocol) 是最核心的協定，負責尋址和路由。其他協定如 ICMP (網際網路控制訊息協定) 也屬於此層。

4. 網路介面層 (Network Interface Layer) / 鏈路層 (Link Layer) / 資料鏈路層 (Data Link Layer)

   • 功能： 負責在同一物理鏈路（如乙太網路、Wi-Fi）上的兩個直接相鄰節點之間傳輸資料訊框（frame）。它處理實體位址（如 MAC 位址），並可能包含錯誤偵測（但通常不包含錯誤修正）。
   • 常見協定/技術： Ethernet (乙太網路)、Wi-Fi (IEEE 802.11)、PPP (點對點協定) 等。

註：有時也會將實體層（Physical Layer）獨立出來，形成五層模型。在該模型中，網路介面層會被細分為資料鏈路層和實體層。

(b) CSMA/CD 與 TCP 的重傳機制差異

CSMA/CD (Carrier Sense Multiple Access with Collision Detection) 是一種用於早期乙太網路（共享式網路）的鏈路層（資料鏈路層）存取控制協定。TCP (Transmission Control Protocol) 是一種傳輸層協定。它們都需要重傳機制，但原因和方式截然不同。

1. 為什麼需要重傳訊息？

本題考查二元樹（Binary Tree）的儲存結構、遍歷方法，以及在不同儲存方式下的記憶體使用分析。

(a) 二元樹的儲存與遍歷方法

二元樹是一種基礎的樹狀資料結構，其中每個節點最多有兩個子節點，通常稱為左子節點（left child）和右子節點（right child）。

(1) 使用陣列 (Array) 儲存與遍歷

• 儲存方法：

  • 陣列儲存法通常用於儲存滿二元樹 (Full Binary Tree) 或完全二元樹 (Complete Binary Tree)。
  • 根節點儲存在陣列索引 0 或 1（取決於習慣，這裡假設索引 0）。
  • 對於索引為 $i$ 的節點：
    • 其左子節點位於索引 $2i + 1$。
    • 其右子節點位於索引 $2i + 2$。
  • 反之，如果一個節點位於索引 $j$：
    • 其父節點（如果存在）位於索引 $\lfloor \frac{j-1}{2} \rfloor$。
  • 如果陣列中有空位（例如，對於非完全二元樹，某些子節點不存在），則用一個特殊值（如 NULL 或 -1）表示。
  • 優點： 結構簡單，存取父子節點非常快速（O(1)），不需要額外的指標空間。
  • 缺點： 對於稀疏的二元樹（例如，只有左子樹或右子樹的樹），會浪費大量陣列空間。需要預先知道或估計樹的最大大小，否則可能需要動態陣列，增加複雜性。

• 遍歷方法 (Traversal)：

  • 陣列儲存的遍歷方法與基於指標的遍歷方法基本相同，但存取節點時使用陣列索引計算。
  • 深度優先遍歷 (Depth-First Traversal)：
    • 前序遍歷 (Preorder Traversal)： 訪問節點 -> 訪問左子樹 -> 訪問右子樹。
    • 中序遍歷 (Inorder Traversal)： 訪問左子樹 -> 訪問節點 -> 訪問右子樹。
    • 後序遍歷 (Postorder Traversal)： 訪問左子樹 -> 訪問右子樹 -> 訪問節點。
    • 這些遍歷通常使用遞迴實現，或使用堆疊（stack）模擬遞迴。
  • 廣度優先遍歷 (Breadth-First Traversal)：
    • 層序遍歷 (Level Order Traversal)： 按照從上到下、從左到右的順序訪問節點。
    • 這通常使用佇列（queue）實現。在陣列儲存中，這與按索引順序掃描陣列（並跳過表示 NULL 的位置）非常相似。

(2) 使用結構與指標 (Structure with Pointers) 儲存與遍歷

• 儲存方法：

  • 這是二元樹最常見的儲存方式，適用於任何結構的二元樹，包括稀疏樹。
  • 每個節點是一個結構（或物件），包含：
    • 節點的資料（Data）。
    • 一個指向左子節點的指標 (Pointer to left child)。
    • 一個指向右子節點的指標 (Pointer to right child)。
  • 如果節點沒有左子節點或右子節點，對應的指標通常設為 NULL。
  • 優點： 空間效率高，只為實際存在的節點及其指標分配空間，不浪費。結構靈活，易於插入、刪除節點。
  • 缺點： 存取父子節點需要透過指標，時間複雜度為 O(1)，但實際存取可能比陣列稍慢（因為需要解引用指標）。每個節點都需要額外的指標空間。

• 遍歷方法 (Traversal)：

  • 遍歷方法與陣列儲存的基本邏輯相同，但存取子節點時是透過結構中的指標。
  • 深度優先遍歷 (Preorder, Inorder, Postorder)： 通常使用遞迴實現，遞迴函數接收當前節點指標作為參數。

    // 遞迴前序遍歷範例
    void preorder(Node* node) {
        if (node == NULL) return;
        visit(node->data); // 訪問節點
        preorder(node->left); // 遍歷左子樹
        preorder(node->right); // 遍歷右子樹
    }
    

  • 廣度優先遍歷 (Level Order)： 使用佇列。將根節點放入佇列，然後循環執行：取出佇列中的節點，訪問它，然後將其左子節點和右子節點（如果存在）放入佇列。

    // 層序遍歷範例
    void levelOrder(Node* root) {
        if (root == NULL) return;
        Queue q;
        q.enqueue(root);
        while (!q.isEmpty()) {
            Node* current = q.dequeue();
            visit(current->data); // 訪問節點
            if (current->left != NULL) q.enqueue(current->left);
            if (current->right != NULL) q.enqueue(current->right);
        }
    }
    

(b) 陣列儲存與指標結構儲存的記憶體比較分析

假設：

• 樹有 $N$ 個節點。
• 樹有 $L$ 層（根節點在第 1 層）。
• 每個節點的資料大小為 $A$ 位元組。
• 每個指標的大小為 $B$ 位元組。

1. 指標結構儲存的記憶體使用：

• 每個節點需要儲存資料 $A$。
• 每個節點需要儲存兩個指標（左和右），總共 $2B$。
• 因此，每個節點的總記憶體使用為 $A + 2B$。
• 總記憶體使用（忽略額外的佇列/堆疊空間）：$N \times (A + 2B)$。

本題考查漸進符號（Asymptotic Notation），特別是 $\Theta$ 符號的定義，並要求證明或證偽給定的漸進關係。

$\Theta(g(n))$ 的定義是：$f(n) = \Theta(g(n))$ 當且僅當存在正常數 $c_1, c_2, n_0$ 使得對於所有 $n \ge n_0$，都滿足 $c_1 g(n) \le f(n) \le c_2 g(n)$。

(a) 證明 $5n^2 - 6n = \Theta(n^2)$

我們要證明存在正常數 $c_1, c_2, n_0$ 使得對於所有 $n \ge n_0$，都滿足 $c_1 n^2 \le 5n^2 - 6n \le c_2 n^2$。

1. 證明 $5n^2 - 6n \le c_2 n^2$：

   • 我們需要找到一個 $c_2$ 和 $n_0$，使得對於所有 $n \ge n_0$， $5n^2 - 6n \le c_2 n^2$ 成立。
   • 考慮 $n > 0$。我們希望 $5n^2 - 6n \le c_2 n^2$。
   • 如果 $n=1$， $5(1)^2 - 6(1) = 5 - 6 = -1$。
   • 如果 $n=2$， $5(2)^2 - 6(2) = 5(4) - 12 = 20 - 12 = 8$。
   • 如果 $n=6$， $5(6)^2 - 6(6) = 5(36) - 36 = 180 - 36 = 144$。
   • 為了簡化，我們觀察 $5n^2 - 6n$。當 $n$ 足夠大時，$5n^2$ 是主導項。
   • 我們要確保 $5n^2 - 6n$ 不會超過 $c_2 n^2$。
   • 對於 $n \ge 1$， $6n \ge 0$。
   • 考慮 $n \ge 6$。此時 $6n \le n^2$。
   • $5n^2 - 6n \le 5n^2$ (當 $6n \ge 0$)。
   • 我們需要確保 $5n^2 - 6n$ 始終小於或等於某個 $c_2 n^2$。
   • 考慮 $n \ge 1$。 $5n^2 - 6n \le 5n^2$。
   • 為了讓 $5n^2 - 6n \le c_2 n^2$ 成立，我們可以讓 $c_2$ 比較大。
   • 例如，取 $c_2 = 5$。則需要 $5n^2 - 6n \le 5n^2$，即 $-6n \le 0$，這對於 $n \ge 0$ 成立。
   • 但是，我們需要 $c_1 g(n) \le f(n)$。
   • 我們需要 $5n^2 - 6n \ge c_1 n^2$。
   • 當 $n=1$, $5n^2 - 6n = -1$。
   • 當 $n=2$, $5n^2 - 6n = 8$。
   • 當 $n=3$, $5n^2 - 6n = 5(9) - 18 = 45 - 18 = 27$。
   • 當 $n=6$, $5n^2 - 6n = 144$。
   • 對於 $n \ge 1$， $5n^2 - 6n$ 可能是負數。但 $\Theta$ 符號通常定義在正函數上，或者要求 $f(n)$ 和 $g(n)$ 對 $n \ge n_0$ 保持相同的符號。
   • 如果 $f(n)$ 可以為負，則 $c_1$ 也可以為負。但定義說 $c_1, c_2$ 是「正常數」（positive constants）。
   • 這意味著 $f(n)$ 和 $g(n)$ 對於 $n \ge n_0$ 都必須是正數。
   • $g(n) = n^2$，當 $n \ge 1$ 時是正數。
   • $f(n) = 5n^2 - 6n$。當 $n$ 較小時，它為負。
     • $5n^2 - 6n > 0 \Rightarrow n(5n - 6) > 0$。由於 $n>0$，所以 $5n - 6 > 0 \Rightarrow 5n > 6 \Rightarrow n > 6/5 = 1.2$。
   • 所以，我們需要選擇 $n_0 > 1.2$。我們選擇 $n_0 = 2$。
   • 對於 $n \ge 2$， $5n^2 - 6n$ 是正數。

   證明 $5n^2 - 6n \le c_2 n^2$ (對於 $n \ge 2$)：

   • 我們需要 $5n^2 - 6n \le c_2 n^2$。
   • $5n^2 - 6n \le 5n^2$ 對於 $n \ge 0$ 成立。
   • 所以，我們可以選擇 $c_2 = 5$。
   • 對於所有 $n \ge 2$， $5n^2 - 6n \le 5n^2$ 成立。

   證明 $c_1 n^2 \le 5n^2 - 6n$ (對於 $n \ge 2$)：

   • 我們需要找到一個 $c_1 > 0$ 和 $n_0$，使得對於所有 $n \ge n_0$， $c_1 n^2 \le 5n^2 - 6n$ 成立。
   • $c_1 n^2 \le 5n^2 - 6n$
   • $6n \le (5 - c_1) n^2$
   • $6 \le (5 - c_1) n$ (假設 $n > 0$)
   • $n \ge \frac{6}{5 - c_1}$
   • 為了讓這個不等式成立，我們需要 $5 - c_1 > 0$，即 $c_1 < 5$。

本題要求將一個遞迴版本的階乘計算函數改寫成非遞迴（迭代）版本。

遞迴函數 fact(N) 的定義是：

• 如果 $N=1$，則返回 1。
• 否則，返回 $N \times \text{fact}(N-1)$。

例如：
fact(5) = 5 * fact(4)
fact(4) = 4 * fact(3)
fact(3) = 3 * fact(2)
fact(2) = 2 * fact(1)
fact(1) = 1

將這些代入，得到 fact(5) = 5 * 4 * 3 * 2 * 1 = 120。

為了將遞迴改為迭代，我們需要模擬遞迴調用的過程，通常使用迴圈和一個變數來累積結果。

迭代方法：

1. 初始化一個變數來儲存階乘的結果，通常稱為 result 或 factorial。由於階乘的乘法性質，它應該初始化為 1（乘法的單位元素）。
2. 使用一個迴圈，從 1 或 2 開始，一直乘到 N。
3. 在每次迴圈迭代中，將當前的乘數乘以累積結果。
4. 迴圈結束後，累積結果就是 N 的階乘。

考慮邊界條件：

• 題目要求計算「正數 N」的階乘。
• 階乘的定義通常是針對非負整數。
• $0! = 1$。
• $1! = 1$。
• 遞迴函數的基礎情況是 $N=1$，返回 1。
• 如果輸入 $N=0$，遞迴函數會進入無限遞迴（因為 fact(0) 會調用 fact(-1)，依此類推）。
• 在改寫的迭代版本中，我們也需要考慮 $N=0$ 或 $N < 0$ 的情況。通常，對於負數，階乘是未定義的。對於 $N=0$，階乘定義為 1。

改寫程式碼：

假設輸入的 $N$ 總是正數（根據題目描述）。
如果 $N=1$，結果是 1。
如果 $N>1$，我們需要從 1 乘到 $N$。

int fact_iterative(int N) {
  // 處理輸入 N < 1 的情況，根據題目要求，N 是正數，所以 N >= 1。
  // 如果允許 N=0，則需要額外處理。
  // 假設 N >= 1
  if (N < 1) {
    // 根據題目要求，N 是正數，此情況理論上不發生。
    // 如果需要嚴謹處理，可以返回錯誤值或拋出異常。
    // 這裡假設 N 總是 >= 1。
    return -1; // 表示錯誤，或根據題目定義處理
  }

  int result = 1; // 初始化結果為 1 (乘法的單位元)

  // 從 2 乘到 N。如果 N=1，迴圈不會執行，result 仍為 1，這是正確的。
  for (int i = 2; i <= N; ++i) {
    result *= i; // 將當前數字 i 乘到結果中
  }

  return result;
}

更簡潔的版本，考慮 $N=0$ 的情況：
如果題目允許 $N \ge 0$，則：

本題要求將一個使用 for 迴圈的程式片段改寫成使用 while 迴圈。

原 for 迴圈結構：

for (initialization; condition; update) {
  // loop body
}

等價於 while 迴圈結構：

initialization;
while (condition) {
  // loop body
  update;
}

原程式碼：

for (i = 0; i<100; i++) {
  if (i % 2 == 0){
    print (i)
  }
}

這個程式碼的目的是從 0 開始，列印出所有小於 100 的偶數。

轉換步驟：

1. 初始化 (initialization)： for 迴圈中的 i = 0; 對應到 while 迴圈前的初始化。
2. 條件 (condition)： for 迴圈中的 i < 100 對應到 while 迴圈的條件。
3. 迴圈體 (loop body)： for 迴圈中的 if (i % 2 == 0) { print (i) } 保持不變，放在 while 迴圈內部。
4. 更新 (update)： for 迴圈中的 i++ 對應到 while 迴圈內部的更新語句，通常放在迴圈體的最後。

改寫後的 while 迴圈程式碼：

核心觀念

本題要求設計一部圖靈機，將輸入的正整數減去 $1$。題目未指定整數的編碼方式，以下採用最常見的假設：

• 輸入以二進位表示。
• 輸入不含前導零，例如 $1000_2$、$101_2$。
• 輸入整數大於零。
• 輸出仍以二進位表示，且除了數字 $0$ 外不含前導零。

二進位減一的規則如下：

1. 從最右端開始借位。
2. 尾端連續的 $0$ 全部改成 $1$。
3. 遇到最右側的 $1$ 時，將它改成 $0$。
4. 若該 $1$ 是最高位，刪除產生的前導零。

例如：

$$1011000_2 \rightarrow 1010111_2$$

解題方法

使用單帶、確定型圖靈機。磁帶格式如下：

$$\triangleright\; w\; \square$$

其中：

• $\triangleright$：輸入左端標記，不可改寫。
• $w \in \{0,1\}^+$：二進位輸入。
• $\square$：空白符號。

圖靈機先向右掃描至輸入末端，再向左執行借位：

• 讀到 $0$：改寫為 $1$，繼續向左借位。
• 讀到 $1$：改寫為 $0$，借位結束。
• 若改寫的 $0$ 位於最高位，則刪除它；但輸入為 $1$ 時，結果應保留為 $0$。

圖靈機定義

令圖靈機為

$$M=(Q,\Sigma,\Gamma,\delta,q_s,q_h)$$

其中：

• 狀態集合：

$$Q=\{q_s,q_b,q_c,q_t,q_e,q_h\}$$

• 輸入字母表：

$$\Sigma=\{0,1\}$$

• 磁帶字母表：

$$\Gamma=\{0,1,\square,\triangleright\}$$

• 初始狀態：$q_s$
• 停止狀態：$q_h$

移動方向 $L$ 表示向左，$R$ 表示向右，$S$ 表示停留。

狀態意義

• $q_s$：向右掃描，尋找輸入末端。
• $q_b$：執行二進位借位。
• $q_c$：確認剛改寫的 $0$ 是否為最高位。
• $q_t$：判斷輸入是否原本只有一個位元。
• $q_e$：刪除多餘的最高位 $0$。
• $q_h$：停止。

轉移函數

目前狀態	讀取符號	寫入符號	移動	下一狀態	說明
$q_s$	$0$	$0$	$R$	$q_s$	向右掃描
$q_s$	$1$	$1$	$R$	$q_s$	向右掃描
$q_s$	$\square$	$\square$	$L$	$q_b$	到達最右端，開始借位
$q_b$	$0$	$1$	$L$	$q_b$	$0$ 借位後變成 $1$
$q_b$	$1$	$0$	$L$	$q_c$	$1$ 減去借位後變成 $0$
$q_c$	$0$	$0$	$S$	$q_h$	左側仍有位元，借位完成
$q_c$	$1$	$1$	$S$	$q_h$	左側仍有位元，借位完成