構造用於加法的圖靈機

通常在不同的有限自動機中，數字以二進位制格式表示。

示例 − 2- 010

     3- 011

     4- 100

但是，在使用圖靈機進行加法的情況下，系統遵循一元格式。

示例 − 2- 11 或 00

     3- 111 或 000

     4- 1111 或 0000

在一元格式中，數字表示為

因此，讓我們考慮使用零來表示圖靈機中用於加法的任何數字。

示例

輸入 4 和 5

4=0000

5=00000

那麼 4+5= 0000c00000

這兩個數字由一個臨時變數 c 分隔，用於表示這兩個數字

輸出：000000000 = 9

圖靈機 (TM) 如下所示：

解釋

步驟 1 − 將 0 轉換為 X，跳轉到步驟 3。

步驟 2 − 如果符號是“c”，則將其轉換為空格，向右移動並跳轉到步驟 6。

步驟 3 − 忽略 0 並向右移動。忽略“c”，然後向右移動。

步驟 4 − 忽略 0 並向右移動。將空格轉換為 0，然後向左移動。

步驟 5 − 忽略 0 並向左移動。

步驟 6 − 忽略“c”，向左移動。

步驟 7 − 忽略 0 並向左移動。

步驟 8 − 忽略 X，向左移動並跳轉到步驟 1。

Bhanu Priya

更新於：2021年6月15日

9K+ 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習